{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,20]],"date-time":"2025-11-20T19:05:11Z","timestamp":1763665511812,"version":"3.41.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"7","license":[{"start":{"date-parts":[[2024,7,1]],"date-time":"2024-07-01T00:00:00Z","timestamp":1719792000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF","award":["2106444"],"award-info":[{"award-number":["2106444"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Commun. ACM"],"published-print":{"date-parts":[[2024,7]]},"abstract":"<jats:p>\n            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            <jats:italic>n<\/jats:italic>\n            \u00d7\n            <jats:italic>n<\/jats:italic>\n            linear system\n            <jats:italic>Ax<\/jats:italic>\n            =\n            <jats:italic>b<\/jats:italic>\n            is\n            <jats:italic>\u00d5<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\u03c9<\/jats:sup>\n            ), where \u03c9 is the matrix multiplication exponent. Improving on this has been an open problem even for sparse linear systems with poly(\n            <jats:italic>n<\/jats:italic>\n            ) condition number.\n          <\/jats:p>\n          <jats:p>\n            In this paper, we present an algorithm that solves linear systems with sparse coefficient matrices asymptotically faster than matrix multiplication for any \u03c9 &gt; 2. This speedup holds for any input matrix\n            <jats:italic>A<\/jats:italic>\n            with\n            <jats:italic>o<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\u03c9\u22121<\/jats:sup>\n            \/ log (\u03ba(\n            <jats:italic>A<\/jats:italic>\n            ))) non-zeros, where \u03ba(\n            <jats:italic>A<\/jats:italic>\n            ) is the condition number of\n            <jats:italic>A<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>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.<\/jats:p>","DOI":"10.1145\/3615679","type":"journal-article","created":{"date-parts":[[2024,7,1]],"date-time":"2024-07-01T20:20:43Z","timestamp":1719865243000},"page":"79-86","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Solving Sparse Linear Systems Faster than Matrix Multiplication"],"prefix":"10.1145","volume":"67","author":[{"given":"Richard","family":"Peng","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Santosh S.","family":"Vempala","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, GA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,7,2]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479892230031"},{"issue":"9","key":"e_1_3_1_3_2","first-page":"1024","article-title":"Computing over the reals: Where Turing meets Newton","volume":"51","author":"Blum L","year":"2004","unstructured":"Blum, L . Computing over the reals: Where Turing meets Newton. Notices of the AMS 51, 9 (2004), 1024\u20131034.","journal-title":"Notices of the AMS"},{"issue":"4","key":"e_1_3_1_4_2","first-page":"1","article-title":"The best of the 20th century: Editors name top 10 algorithms","volume":"33","author":"Cipra B.A","year":"2000","unstructured":"Cipra, B.A . The best of the 20th century: Editors name top 10 algorithms. SIAM news 33, 4 (2000), 1\u20132; https:\/\/archive.siam.org\/pdf\/news\/637.pdf.","journal-title":"SIAM news"},{"key":"e_1_3_1_5_2","doi-asserted-by":"crossref","unstructured":"Demmel J. Dumitriu I. Holtz O. and Kleinberg R. Fast matrix multiplication is stable. Numerische Mathematik 106 2 (2007) 199\u2013224.","DOI":"10.1007\/s00211-007-0061-6"},{"key":"e_1_3_1_6_2","doi-asserted-by":"crossref","unstructured":"Eberly W. et al. Faster inversion and other black box matrix computations using efficient block projections. In Symbolic and Algebraic Computation Intern. Symp. ISSAC 2007 Waterloo Ontario Canada July 28 - August 1 2007 Proceedings 2007 143\u2013150.","DOI":"10.1145\/1277548.1277569"},{"key":"e_1_3_1_7_2","doi-asserted-by":"crossref","unstructured":"Ghadiri M. Peng R. and Vempala S.S. The bit complexity of efficient continuous optimization. In\u00a0Proceedings of the 64th Symp. on Foundations of Computer Science 2023; https:\/\/arxiv.org\/abs\/2304.02124.","DOI":"10.1109\/FOCS57990.2023.00125"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.5555\/1202296"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/2347736.2347759"},{"key":"e_1_3_1_10_2","volume-title":"Approximate Gaussian Elimination","author":"Kyng R","year":"2017","unstructured":"Kyng, R . Approximate Gaussian Elimination. PhD thesis, Yale University, 2017; http:\/\/rasmuskyng.com\/rjkyng-dissertation.pdf."},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.17"},{"key":"e_1_3_1_12_2","unstructured":"Luh K. and Vu V. Sparse random matrices have simple spectrum. arXiv preprint arXiv:1802.03662 2018."},{"key":"e_1_3_1_13_2","doi-asserted-by":"crossref","unstructured":"Musco C. Musco C. and Sidford A. Stability of the Lanczos method for matrix function approximation. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symp. on Discrete Algorithms SODA 2018 New Orleans LA USA January 7-10 2018 2018 1605\u20131624; https:\/\/arxiv.org\/abs\/1708.07788.","DOI":"10.1137\/1.9781611975031.105"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-016-0693-5"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520060"},{"key":"e_1_3_1_16_2","first-page":"1576","volume-title":"Proceedings of the Intern. Congress of Mathematicians 2010 (ICM 2010) (In 4 Volumes) Vol. I: Plenary Lectures and Ceremonies Vols. II\u2013IV: Invited Lectures","author":"Rudelson M.","year":"2010","unstructured":"Rudelson, M. and Vershynin, R. Non-asymptotic theory of random matrices: extreme singular values. In Proceedings of the Intern. Congress of Mathematicians 2010 (ICM 2010) (In 4 Volumes) Vol. I: Plenary Lectures and Ceremonies Vols. II\u2013IV: Invited Lectures. World Scientific, 2010, 1576\u20131602"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.5555\/829576"},{"issue":"2","key":"e_1_3_1_18_2","first-page":"125","article-title":"Faster algorithms via approximation theory","volume":"9","author":"Sachdeva S.","year":"2013","unstructured":"Sachdeva, S. and Vishnoi, N.K. Faster algorithms via approximation theory. Theoretical Computer Science 9, 2 (2013), 125\u2013210.","journal-title":"Theoretical Computer Science"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479803436202"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1137\/090771430"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.5555\/1108638.1716354"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-2010-02396-8"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1561\/2200000048"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1561\/0400000060"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1137\/120895755"},{"key":"e_1_3_1_26_2","volume-title":"Hardness and Tractability For Structured Numerical Problems","author":"Zhang P","year":"2018","unstructured":"Zhang, P . Hardness and Tractability For Structured Numerical Problems. PhD thesis, Georgia Institute of Technology, 2018."}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3615679","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3615679","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:10:17Z","timestamp":1750295417000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3615679"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7]]},"references-count":25,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2024,7]]}},"alternative-id":["10.1145\/3615679"],"URL":"https:\/\/doi.org\/10.1145\/3615679","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"type":"print","value":"0001-0782"},{"type":"electronic","value":"1557-7317"}],"subject":[],"published":{"date-parts":[[2024,7]]},"assertion":[{"value":"2024-07-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}