Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers
ACM Transactions on Algorithms · 31.07.2025 · 21 (3) · 1-49
DOI: 10.1145/3593809 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Algorithms, online erschienen am 26.07.2025. Verfasst von Arun Jambulapati und 1 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 43 Literaturangaben. Gefördert von: NSF CAREER Award.
Abstract (Originalsprache)
In this article, we provide an O ( m loglog O (1) n log (1/ε))-expected time algorithm for solving Laplacian systems on n -node m -edge graphs, improving upon the previous best expected runtime of \(O(m \sqrt {\log n} \mathrm{log log}^{O(1)} n \log (1/\epsilon))\) achieved by Cohen et al. [ 12 ]. To obtain this result, we provide efficient constructions of low spectral stretch graph approximations with improved stretch and sparsity bounds. As motivation for this work, we show that, for every set of vectors in \(\mathbb {R}^d\) (not just those induced by graphs) and all integer k > 1, there exist an ultra-sparsifier with d -1 + O ( d/k ) re-weighted vectors of relative condition number at most k 2 . For small k , this improves upon the previous best known multiplicative factor of \(k \cdot \tilde{O}(\log d)\) , which is only known for the graph case. Additionally, in the graph case, we employ our low-stretch subgraph construction to obtain n - 1 + O ( n/k )-edge ultrasparsifiers of relative condition number k 1+o(1) for k = ω (log δ n ) for any δ > 0: this improves upon the previous work for k = o (exp (log 1/2-δ n )).
Förderung
- NSF CAREER Award
Zitieren
APA
Jambulapati, A., & Sidford, A. (2025). Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers. ACM Transactions on Algorithms, 21(3), 1-49. https://doi.org/10.1145/3593809
Vancouver
Jambulapati A, Sidford A. Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers. ACM Transactions on Algorithms. 2025;21(3):1-49. doi:10.1145/3593809
BibTeX
@article{Jambulapati2025,
author = {Jambulapati, Arun and Sidford, Aaron},
title = {Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers},
journal = {ACM Transactions on Algorithms},
year = {2025},
volume = {21},
number = {3},
pages = {1--49},
doi = {10.1145/3593809}
}
EUVIMED