EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Solving Sparse Linear Systems Faster than Matrix Multiplication

Richard Peng, Santosh S. Vempala

Communications of the ACM · 2024-07 · 67 (7) · 79-86

DOI: 10.1145/3615679 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Communications of the ACM, online erschienen am 02.07.2024. Verfasst von Richard Peng und 1 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 25 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: NSF.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Can linear systems be solved faster than matrix multiplication? While there has been remarkable progress for the special cases of graph-structured linear systems, in the general setting, the bit complexity of solving an n × n linear system Ax = b is Õ ( n ω ), where ω is the matrix multiplication exponent. Improving on this has been an open problem even for sparse linear systems with poly( n ) condition number. In this paper, we present an algorithm that solves linear systems with sparse coefficient matrices asymptotically faster than matrix multiplication for any ω > 2. This speedup holds for any input matrix A with o ( n ω−1 / log (κ( A ))) non-zeros, where κ( A ) is the condition number of A . Our algorithm can be viewed as an efficient, randomized implementation of the block Krylov method via recursive low displacement rank factorization. It is inspired by an algorithm of Eberly et al. for inverting matrices over finite fields. In our analysis of numerical stability, we develop matrix anti-concentration techniques to bound the smallest eigenvalue and the smallest gap in the eigenvalues of semi-random matrices.

Förderung

  • NSF

Zitieren

APA

Peng, R., & Vempala, S. S. (2024). Solving Sparse Linear Systems Faster than Matrix Multiplication. Communications of the ACM, 67(7), 79-86. https://doi.org/10.1145/3615679

Vancouver

Peng R, Vempala SS. Solving Sparse Linear Systems Faster than Matrix Multiplication. Communications of the ACM. 2024;67(7):79-86. doi:10.1145/3615679

BibTeX
@article{Peng2024,
  author = {Peng, Richard and Vempala, Santosh S.},
  title = {Solving Sparse Linear Systems Faster than Matrix Multiplication},
  journal = {Communications of the ACM},
  year = {2024},
  volume = {67},
  number = {7},
  pages = {79--86},
  doi = {10.1145/3615679}
}
Kostenlos starten →