EUVIMEDEUVIMED entdecken
Crossref

Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers

Arun Jambulapati, Aaron Sidford

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →