Entrywise Approximate Laplacian Solving
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916396048318464 |
|---|---|
| author | Chen, Jingbang Ghadiri, Mehrdad Nguyen, Hoai-An Peng, Richard Yang, Junzhao |
| author_facet | Chen, Jingbang Ghadiri, Mehrdad Nguyen, Hoai-An Peng, Richard Yang, Junzhao |
| contents | We study the escape probability problem in random walks over graphs. Given vertices, $s,t,$ and $p$, the problem asks for the probability that a random walk starting at $s$ will hit $t$ before hitting $p$. Such probabilities can be exponentially small even for unweighted undirected graphs with polynomial mixing time. Therefore current approaches, which are mostly based on fixed-point arithmetic, require $n$ bits of precision in the worst case. We present algorithms and analyses for weighted directed graphs under floating-point arithmetic and improve the previous best running times in terms of the number of bit operations. We believe our techniques and analysis could have a broader impact on the computation of random walks on graphs both in theory and in practice. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_10022 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Entrywise Approximate Laplacian Solving Chen, Jingbang Ghadiri, Mehrdad Nguyen, Hoai-An Peng, Richard Yang, Junzhao Data Structures and Algorithms We study the escape probability problem in random walks over graphs. Given vertices, $s,t,$ and $p$, the problem asks for the probability that a random walk starting at $s$ will hit $t$ before hitting $p$. Such probabilities can be exponentially small even for unweighted undirected graphs with polynomial mixing time. Therefore current approaches, which are mostly based on fixed-point arithmetic, require $n$ bits of precision in the worst case. We present algorithms and analyses for weighted directed graphs under floating-point arithmetic and improve the previous best running times in terms of the number of bit operations. We believe our techniques and analysis could have a broader impact on the computation of random walks on graphs both in theory and in practice. |
| title | Entrywise Approximate Laplacian Solving |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2409.10022 |