{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,24]],"date-time":"2025-11-24T16:41:15Z","timestamp":1764002475180,"version":"3.45.0"},"reference-count":85,"publisher":"Association for Computing Machinery (ACM)","issue":"6","funder":[{"name":"NSF CAREER","award":["1846218"],"award-info":[{"award-number":["1846218"]}]},{"name":"NSF","award":["AF-1909756 and AF-2007443"],"award-info":[{"award-number":["AF-1909756 and AF-2007443"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2025,12,31]]},"abstract":"<jats:p>\n                    Can linear systems be solved faster than matrix multiplication? Although there has been much progress on systems with additional structures, in the general setting, the complexity of solving an\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    \u00d7\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    linear system\n                    <jats:italic toggle=\"yes\">Ax<\/jats:italic>\n                    =\n                    <jats:italic toggle=\"yes\">b<\/jats:italic>\n                    is at least \u03a9 (\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    <jats:sup>\u03c9<\/jats:sup>\n                    ) bit operations, where \u03c9 &lt; 2.372 is the matrix multiplication exponent. Improving on this bound of\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    <jats:sup>&lt;<\/jats:sup>\n                    has been an open problem even for sparse linear systems with poly(\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    ) condition number.\n                  <\/jats:p>\n                  <jats:p>\n                    In this article, we present an algorithm that solves linear systems in sparse matrices asymptotically faster than matrix multiplication or any \u03c9 &gt; 2. This speedup holds for any input matrix\n                    <jats:italic toggle=\"yes\">A<\/jats:italic>\n                    with\n                    <jats:italic toggle=\"yes\">o<\/jats:italic>\n                    (\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    <jats:sup>\u03c9-1<\/jats:sup>\n                    \/log (\u03ba (A))) nonzeros, where \u03ba (\n                    <jats:italic toggle=\"yes\">A<\/jats:italic>\n                    ) is the condition number of\n                    <jats:italic toggle=\"yes\">A<\/jats:italic>\n                    . For poly(\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    )-conditioned matrices with \u00d5(\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    ) nonzeros, and the current value of \u03c9, the bit complexity of our algorithm to solve to within any 1\/poly(\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    ) error is\n                    <jats:italic toggle=\"yes\">O<\/jats:italic>\n                    (\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    <jats:sup>2.331<\/jats:sup>\n                    ).\n                  <\/jats:p>\n                  <jats:p>\n                    Our algorithm can be viewed as an efficient, randomized implementation of the block Krylov method via recursive low displacement rank factorizations. It is inspired by the algorithm of [Eberly et\u00a0al. ISSAC \u201806 \u201807] for inverting matrices over finite fields. In our analysis of numerical stability, we use matrix anti-concentration techniques to bound the smallest eigenvalue and the smallest gap in eigenvalues of semi-random matrices. Incorporating the matrix anti-concentration bounds by [Nie STOC\u201822] gives an improved bit complexity of\n                    <jats:italic toggle=\"yes\">O<\/jats:italic>\n                    (\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    <jats:sup>2.271<\/jats:sup>\n                    ).\n                  <\/jats:p>","DOI":"10.1145\/3767721","type":"journal-article","created":{"date-parts":[[2025,9,15]],"date-time":"2025-09-15T11:30:22Z","timestamp":1757935822000},"page":"1-72","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Solving Sparse Linear Systems Faster than Matrix Multiplication"],"prefix":"10.1145","volume":"72","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5407-7965","authenticated-orcid":false,"given":"Richard","family":"Peng","sequence":"first","affiliation":[{"name":"Computer Science, Carnegie Mellon University","place":["Pittsburgh, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3779-433X","authenticated-orcid":false,"given":"Santosh","family":"Vempala","sequence":"additional","affiliation":[{"name":"Computer Science, Georgia Institute of Technology","place":["Atlanta, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,11,24]]},"reference":[{"issue":"03","key":"e_1_3_4_2_2","doi-asserted-by":"crossref","first-page":"1750028","DOI":"10.1142\/S0219199717500286","article-title":"Matrix regularizing effects of Gaussian perturbations","volume":"19","author":"Aizenman Michael","year":"2017","unstructured":"Michael Aizenman, Ron Peled, Jeffrey Schenker, Mira Shamis, and Sasha Sodin. 2017. Matrix regularizing effects of Gaussian perturbations. Communications in Contemporary Mathematics 19, 03 (2017), 1750028.","journal-title":"Communications in Contemporary Mathematics"},{"key":"e_1_3_4_3_2","doi-asserted-by":"crossref","first-page":"2005","DOI":"10.1137\/1.9781611978322.63","volume-title":"Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025","author":"Alman Josh","year":"2025","unstructured":"Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. 2025. More asymmetry yields faster matrix multiplication. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025. Yossi Azar and Debmalya Panigrahi (Eds.), SIAM, 2005\u20132039. Retrieved fromhttps:\/\/arxiv.org\/abs\/2404.16349"},{"key":"e_1_3_4_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/S10208-022-09577-5"},{"issue":"3","key":"e_1_3_4_5_2","doi-asserted-by":"crossref","first-page":"804","DOI":"10.1137\/S0895479892230031","article-title":"A uniform approach for the fast computation of matrix-type Pad\u00e9 approximants","volume":"15","author":"Beckermann Bernhard","year":"1994","unstructured":"Bernhard Beckermann and George Labahn. 1994. A uniform approach for the fast computation of matrix-type Pad\u00e9 approximants. SIAM Journal on Matrix Analysis and Applications 15, 3 (1994), 804\u2013823.","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"key":"e_1_3_4_6_2","doi-asserted-by":"crossref","unstructured":"Robert R. Bitmead and Brian D. O. Anderson. 1980. Asymptotically fast solution of Toeplitz and related systems of linear equations. Linear Algebra Appl. 34 1 (1980) 103\u2013116.","DOI":"10.1016\/0024-3795(80)90161-5"},{"key":"e_1_3_4_7_2","doi-asserted-by":"crossref","DOI":"10.1017\/9781108755528","volume-title":"Foundations of Data Science","author":"Blum Avrim","year":"2020","unstructured":"Avrim Blum, John Hopcroft, and Ravindran Kannan. 2020. Foundations of Data Science. Cambridge University Press."},{"issue":"9","key":"e_1_3_4_8_2","first-page":"1024","article-title":"Computing over the reals: Where Turing meets Newton","volume":"51","author":"Blum Lenore","year":"2004","unstructured":"Lenore Blum. 2004. Computing over the reals: Where Turing meets Newton. Notices of the AMS 51, 9 (2004), 1024\u20131034.","journal-title":"Notices of the AMS"},{"issue":"1","key":"e_1_3_4_9_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/S0273-0979-1989-15750-9","article-title":"On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines","volume":"21","author":"Blum Lenore","year":"1989","unstructured":"Lenore Blum, Mike Shub, and Steve Smale. 1989. On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bulletin (New Series) of the American Mathematical Society 21, 1 (1989), 1\u201346.","journal-title":"Bulletin (New Series) of the American Mathematical Society"},{"issue":"6","key":"e_1_3_4_10_2","doi-asserted-by":"crossref","first-page":"3264","DOI":"10.1137\/040611781","article-title":"Solving elliptic finite element systems in near-linear time with support preconditioners","volume":"46","author":"Boman Erik G.","year":"2008","unstructured":"Erik G. Boman, Bruce Hendrickson, and Stephen A. Vavasis. 2008. Solving elliptic finite element systems in near-linear time with support preconditioners. SIAM Journal on Numerical Analysis 46, 6 (2008), 3264\u20133284.","journal-title":"SIAM Journal on Numerical Analysis"},{"issue":"3","key":"e_1_3_4_11_2","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1137\/16M1062855","article-title":"On matrices with displacement structure: Generalized operators and faster algorithms","volume":"38","author":"Bostan Alin","year":"2017","unstructured":"Alin Bostan, C-P Jeannerod, Christophe Mouilleron, and \u00c9. Schost. 2017. On matrices with displacement structure: Generalized operators and faster algorithms. SIAM Journal on Matrix Analysis and Applications 38, 3 (2017), 733\u2013775.","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"issue":"2","key":"e_1_3_4_12_2","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/BF02772174","article-title":"Invertibility of \u2018Large\u2019 submatrices with applications to the geometry of Banach spaces and harmonic analysis","volume":"57","author":"Bourgain Jean","year":"1987","unstructured":"Jean Bourgain and Lior Tzafriri. 1987. Invertibility of \u2018Large\u2019 submatrices with applications to the geometry of Banach spaces and harmonic analysis. Israel Journal of Mathematics 57, 2 (1987), 137\u2013224.","journal-title":"Israel Journal of Mathematics"},{"key":"e_1_3_4_13_2","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex Optimization","author":"Boyd Stephen","year":"2004","unstructured":"Stephen Boyd, Stephen P. Boyd, and Lieven Vandenberghe. 2004. Convex Optimization. Cambridge University Press."},{"key":"e_1_3_4_14_2","series-title":"LIPIcs","first-page":"33:1\u201333:24","volume-title":"Proceedings of the 13th Innovations in Theoretical Computer Science Conference, ITCS 2022","volume":"215","author":"Casacuberta S\u00edlvia","year":"2022","unstructured":"S\u00edlvia Casacuberta and Rasmus Kyng. 2022. Faster sparse matrix inversion and rank computation in finite fields. In Proceedings of the 13th Innovations in Theoretical Computer Science Conference, ITCS 2022. Mark Braverman (Ed.), LIPIcs, Vol. 215, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 33:1\u201333:24. Retrieved fromhttps:\/\/arxiv.org\/abs\/2106.09830"},{"issue":"4","key":"e_1_3_4_15_2","first-page":"1","article-title":"The best of the 20th century: Editors name top 10 algorithms","volume":"33","author":"Cipra Barry A.","year":"2000","unstructured":"Barry A. Cipra. 2000. The best of the 20th century: Editors name top 10 algorithms. SIAM News 33, 4 (2000), 1\u20132. Retrieved fromhttps:\/\/archive.siam.org\/pdf\/news\/637.pdf","journal-title":"SIAM News"},{"key":"e_1_3_4_16_2","doi-asserted-by":"crossref","first-page":"898","DOI":"10.1109\/FOCS.2018.00089","volume-title":"Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018","author":"Cohen Michael B.","year":"2018","unstructured":"Michael B. Cohen, Jonathan A. Kelner, Rasmus Kyng, John Peebles, Richard Peng, Anup B. Rao, and Aaron Sidford. 2018. Solving directed Laplacian systems in nearly-linear time through sparse LU factorizations. In Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018. Mikkel Thorup (Ed.), IEEE Computer Society, 898\u2013909. Retrieved fromhttps:\/\/arxiv.org\/abs\/1811.10722"},{"key":"e_1_3_4_17_2","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1145\/3055399.3055463","volume-title":"Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017","author":"Cohen Michael B.","year":"2017","unstructured":"Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford, and Adrian Vladu. 2017. Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017. Hamed Hatami, Pierre McKenzie, and Valerie King (Eds.), ACM, 410\u2013419. Retrieved fromhttps:\/\/arxiv.org\/abs\/1611.00755"},{"issue":"3","key":"e_1_3_4_18_2","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1109\/74.250128","article-title":"The fast multipole method for the wave equation: A pedestrian prescription","volume":"35","author":"Coifman Ronald","year":"1993","unstructured":"Ronald Coifman, Vladimir Rokhlin, and Stephen Wandzura. 1993. The fast multipole method for the wave equation: A pedestrian prescription. IEEE Antennas and Propagation Magazine 35, 3 (1993), 7\u201312.","journal-title":"IEEE Antennas and Propagation Magazine"},{"key":"e_1_3_4_19_2","doi-asserted-by":"publisher","DOI":"10.2307\/2153413"},{"key":"e_1_3_4_20_2","first-page":"1","volume-title":"Proceedings of the 19th Annual ACM Symposium on Theory of Computing","author":"Coppersmith Don","year":"1987","unstructured":"Don Coppersmith and Shmuel Winograd. 1987. Matrix multiplication via arithmetic progressions. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing. Alfred V. Aho (Ed.), ACM, 1\u20136."},{"key":"e_1_3_4_21_2","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","year":"2009","unstructured":"Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms(3rd ed.). MIT Press. Retrieved from http:\/\/mitpress.mit.edu\/books\/introduction-algorithms"},{"key":"e_1_3_4_22_2","doi-asserted-by":"crossref","unstructured":"Timothy A. Davis Sivasankaran Rajamanickam and Wissam M. Sid-Lakhdar. 2016. A survey of direct methods for sparse linear systems. Acta Numerica 25 1 (2016) 383\u2013566.","DOI":"10.1017\/S0962492916000076"},{"issue":"1","key":"e_1_3_4_23_2","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/s00211-007-0114-x","article-title":"Fast linear algebra is stable","volume":"108","author":"Demmel James","year":"2007","unstructured":"James Demmel, Ioana Dumitriu, and Olga Holtz. 2007. Fast linear algebra is stable. Numerische Mathematik 108, 1 (2007), 59\u201391.","journal-title":"Numerische Mathematik"},{"issue":"2","key":"e_1_3_4_24_2","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/s00211-007-0061-6","article-title":"Fast matrix multiplication is stable","volume":"106","author":"Demmel James","year":"2007","unstructured":"James Demmel, Ioana Dumitriu, Olga Holtz, and Robert Kleinberg. 2007. Fast matrix multiplication is stable. Numerische Mathematik 106, 2 (2007), 199\u2013224.","journal-title":"Numerische Mathematik"},{"issue":"1","key":"e_1_3_4_25_2","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/BF01459082","article-title":"Exact solution of linear equations using P-adic expansions","volume":"40","author":"Dixon John D.","year":"1982","unstructured":"John D. Dixon. 1982. Exact solution of linear equations using P-adic expansions. Numerische Mathematik 40, 1 (1982), 137\u2013141.","journal-title":"Numerische Mathematik"},{"issue":"2","key":"e_1_3_4_26_2","doi-asserted-by":"crossref","first-page":"844","DOI":"10.1137\/07070471X","article-title":"Relative-error CUR matrix decompositions","volume":"30","author":"Drineas Petros","year":"2008","unstructured":"Petros Drineas, Michael W. Mahoney, and Shan Muthukrishnan. 2008. Relative-error CUR matrix decompositions. SIAM Journal on Matrix Analysis and Applications 30, 2 (2008), 844\u2013881. Retrieved fromhttps:\/\/arxiv.org\/abs\/0708.3696","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"key":"e_1_3_4_27_2","first-page":"63","volume-title":"Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC 2006","author":"Eberly Wayne","year":"2006","unstructured":"Wayne Eberly, Mark Giesbrecht, Pascal Giorgi, Arne Storjohann, and Gilles Villard. 2006. Solving sparse rational linear systems. In Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC 2006. Barry M. Trager (Ed.), ACM, 63\u201370."},{"key":"e_1_3_4_28_2","first-page":"143","volume-title":"Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC 2007","author":"Eberly Wayne","year":"2007","unstructured":"Wayne Eberly, Mark Giesbrecht, Pascal Giorgi, Arne Storjohann, and Gilles Villard. 2007. Faster inversion and other black box matrix computations using efficient block projections. In Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC 2007. Dongming Wang (Ed.), ACM, 143\u2013150. Retrieved fromhttps:\/\/arxiv.org\/abs\/cs\/0701188"},{"key":"e_1_3_4_29_2","volume-title":"Computational Topology: An Introduction","author":"Edelsbrunner Herbert","year":"2010","unstructured":"Herbert Edelsbrunner and John Harer. 2010. Computational Topology: An Introduction. American Mathematical Soc."},{"key":"e_1_3_4_30_2","doi-asserted-by":"crossref","unstructured":"K. A. Gallivan S Thirumalai Paul Van Dooren and V Vermaut. 1996. High performance algorithms for toeplitz and block toeplitz matrices. Linear Algebra and Its Applications 241-243 1 (1996) 343\u2013388.","DOI":"10.1016\/0024-3795(95)00649-4"},{"key":"e_1_3_4_31_2","unstructured":"Mehrdad Ghadiri Richard Peng and Santosh S. Vempala. 2021. Sparse regression faster than d \\({}^{\\mbox{{$\\omega $}}}\\) . arXiv:2109.11537. Retrieved from https:\/\/arxiv.org\/abs\/2109.11537"},{"key":"e_1_3_4_32_2","doi-asserted-by":"crossref","unstructured":"Mehrdad Ghadiri Richard Peng and Santosh S. Vempala. 2023. The bit complexity of efficient continuous optimization. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS). 2059\u20132070. Available at: https:\/\/arxiv.org\/abs\/2304.02124","DOI":"10.1109\/FOCS57990.2023.00125"},{"issue":"12","key":"e_1_3_4_33_2","first-page":"272","article-title":"A formula for the inversion of finite Toeplitz matrices","volume":"7","author":"Gohberg I.","year":"1972","unstructured":"I. Gohberg and N. Ya Krupnik. 1972. A formula for the inversion of finite Toeplitz matrices. Matematicheskie Issledovaniya 7, 12 (1972), 272\u2013283.","journal-title":"Matematicheskie Issledovaniya"},{"issue":"1","key":"e_1_3_4_34_2","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1137\/1031003","article-title":"Some history of the conjugate gradient and Lanczos algorithms: 1948\u20131976","volume":"31","author":"Golub Gene H.","year":"1989","unstructured":"Gene H. Golub and Dianne P. O\u2019Leary. 1989. Some history of the conjugate gradient and Lanczos algorithms: 1948\u20131976. SIAM Review 31, 1 (1989), 50\u2013102.","journal-title":"SIAM Review"},{"key":"e_1_3_4_35_2","volume-title":"Toeplitz and Circulant Matrices: A Review","author":"Gray Robert M.","year":"2006","unstructured":"Robert M. Gray. 2006. Toeplitz and Circulant Matrices: A Review. Now Publishers Inc."},{"key":"e_1_3_4_36_2","volume-title":"Convergence Properties of the Conjugate Gradient Algorithm in Exact and Finite Precision Arithmetic","author":"Greenbaum Anne","year":"1981","unstructured":"Anne Greenbaum. 1981. Convergence Properties of the Conjugate Gradient Algorithm in Exact and Finite Precision Arithmetic. Ph.D. Dissertation. University of California, Berkeley. AAI8200121."},{"key":"e_1_3_4_37_2","volume-title":"Combinatorial Preconditioners for Sparse, Symmetric, Diagonally Dominant Linear Systems","author":"Gremban Keith D.","year":"1996","unstructured":"Keith D. Gremban. 1996. Combinatorial Preconditioners for Sparse, Symmetric, Diagonally Dominant Linear Systems. Ph.D. Dissertation. Carnegie Mellon University, Pittsburgh. CMU CS Tech Report CMU-CS-96-123."},{"key":"e_1_3_4_38_2","doi-asserted-by":"crossref","unstructured":"David Harvey and Joris van der Hoeven. 2022. Polynomial multiplication over finite fields in time \\(O (n log n)\\) . J. ACM 69 2 Article 12 (March 2022) 40 pages.","DOI":"10.1145\/3505584"},{"key":"e_1_3_4_39_2","volume-title":"Methods of Conjugate Gradients for Solving Linear Systems","author":"Hestenes Magnus Rudolph","year":"1952","unstructured":"Magnus Rudolph Hestenes and Eduard Stiefel. 1952. Methods of Conjugate Gradients for Solving Linear Systems. Vol. 49\u20131. NBS Washington, DC."},{"issue":"2","key":"e_1_3_4_40_2","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1016\/0022-247X(79)90124-0","article-title":"Displacement ranks of matrices and linear equations","volume":"68","author":"Kailath Thomas","year":"1979","unstructured":"Thomas Kailath, Sun-Yuan Kung, and Martin Morf. 1979. Displacement ranks of matrices and linear equations. Journal of Mathematical Analysis and Applications 68, 2 (1979), 395\u2013407.","journal-title":"Journal of Mathematical Analysis and Applications"},{"key":"e_1_3_4_41_2","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/3-540-54522-0_93","volume-title":"Proceedings of the 9th International Symposium, on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (AAECC-9)","author":"Kaltofen Erich","year":"1991","unstructured":"Erich Kaltofen and B. David Saunders. 1991. On Wiedemann\u2019s method of solving sparse linear systems. In Proceedings of the 9th International Symposium, on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (AAECC-9). Springer-Verlag, Berlin, 29\u201338."},{"key":"e_1_3_4_42_2","doi-asserted-by":"crossref","unstructured":"Ravindran Kannan and Santosh Vempala. 2017. Randomized algorithms in numerical linear algebra. Acta Numerica 26 1 (2017) 95. https:\/\/www.cc.gatech.edu\/vempala\/papers\/acta_survey.pdf","DOI":"10.1017\/S0962492917000058"},{"key":"e_1_3_4_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/2347736.2347759"},{"key":"e_1_3_4_44_2","volume-title":"Approximate Gaussian Elimination","author":"Kyng Rasmus","year":"2017","unstructured":"Rasmus Kyng. 2017. Approximate Gaussian Elimination. Ph.D. Dissertation. Yale University. Retrieved fromhttp:\/\/rasmuskyng.com\/rjkyng-dissertation.pdf"},{"key":"e_1_3_4_45_2","first-page":"842","volume-title":"Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing","author":"Kyng Rasmus","year":"2016","unstructured":"Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva, and Daniel A. Spielman. 2016. Sparsified Cholesky and multigrid solvers for connection Laplacians. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing. ACM, 842\u2013850. Retrieved fromhttp:\/\/arxiv.org\/abs\/1512.01892"},{"key":"e_1_3_4_46_2","doi-asserted-by":"crossref","first-page":"573","DOI":"10.1109\/FOCS.2016.68","volume-title":"Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016","author":"Kyng Rasmus","year":"2016","unstructured":"Rasmus Kyng and Sushant Sachdeva. 2016. Approximate Gaussian elimination for Laplacians - Fast, sparse, and simple. In Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016. Irit Dinur (Ed.), IEEE Computer Society, 573\u2013582. Retrieved fromhttps:\/\/arxiv.org\/abs\/1605.02353"},{"key":"e_1_3_4_47_2","first-page":"279","volume-title":"Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020","author":"Kyng Rasmus","year":"2020","unstructured":"Rasmus Kyng, Di Wang, and Peng Zhang. 2020. Packing LPs are hard to solve accurately, assuming linear equations are hard. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020. Shuchi Chawla (Ed.), SIAM, 279\u2013296. Retrieved from10.5555\/3381089.3381106"},{"key":"e_1_3_4_48_2","doi-asserted-by":"crossref","first-page":"684","DOI":"10.1109\/FOCS.2017.69","volume-title":"Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017","author":"Kyng Rasmus","year":"2017","unstructured":"Rasmus Kyng and Peng Zhang. 2017. Hardness results for structured linear systems. In Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017. IEEE Computer Society, 684\u2013695. Retrieved fromhttps:\/\/arxiv.org\/abs\/1705.02944"},{"key":"e_1_3_4_49_2","doi-asserted-by":"crossref","unstructured":"George Labahn and Tamir Shalom. 1992. Inversion of Toeplitz matrices with only two standard equations. Linear Algebra and its Applications 175 1 (1992) 143\u2013158.","DOI":"10.1016\/0024-3795(92)90306-U"},{"key":"e_1_3_4_50_2","doi-asserted-by":"crossref","unstructured":"Cornelius Lanczos. 1950. An iteration method for the solution of the eigenvalue problem of linear differential and integral operators. J. Res. Nat. Bur. Standards 45 4 (1950) 255\u2013282.","DOI":"10.6028\/jres.045.026"},{"key":"e_1_3_4_51_2","doi-asserted-by":"crossref","first-page":"296","DOI":"10.1145\/2608628.2608664","volume-title":"Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation","author":"Gall Francois Le","year":"2014","unstructured":"Francois Le Gall. 2014. Powers of tensors and fast matrix multiplication. In Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation. ACM, 296\u2013303. Retrieved fromhttp:\/\/arxiv.org\/abs\/1401.7714"},{"issue":"10","key":"e_1_3_4_52_2","doi-asserted-by":"crossref","first-page":"4071","DOI":"10.1016\/j.jcp.2011.02.033","article-title":"Fast construction of hierarchical matrix representation from matrix\u2013vector multiplication","volume":"230","author":"Lin Lin","year":"2011","unstructured":"Lin Lin, Jianfeng Lu, and Lexing Ying. 2011. Fast construction of hierarchical matrix representation from matrix\u2013vector multiplication. Journal of Computational Physics 230, 10 (2011), 4071\u20134087.","journal-title":"Journal of Computational Physics"},{"key":"e_1_3_4_53_2","doi-asserted-by":"crossref","unstructured":"Patrick Lopatto and Kyle Luh. 2021. Tail bounds for gaps between eigenvalues of sparse random matrices. Electronic Journal of Probability 26 (2021) 1\u201326.","DOI":"10.1214\/21-EJP669"},{"key":"e_1_3_4_54_2","doi-asserted-by":"crossref","unstructured":"Kyle Luh and Van Vu. 2020. Sparse random matrices have simple spectrum. Annales de l\u2019Institut Henri Poincare 56 4 (2020) 2307\u20132328. Available at: https:\/\/arxiv.org\/abs\/1802.03662","DOI":"10.1214\/19-AIHP1032"},{"key":"e_1_3_4_55_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02099544"},{"key":"e_1_3_4_56_2","first-page":"1605","volume-title":"Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018","author":"Musco Cameron","year":"2018","unstructured":"Cameron Musco, Christopher Musco, and Aaron Sidford. 2018. Stability of the Lanczos method for matrix function approximation. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. SIAM, 1605\u20131624. Retrieved fromhttps:\/\/arxiv.org\/abs\/1708.07788"},{"issue":"3","key":"e_1_3_4_57_2","doi-asserted-by":"crossref","first-page":"777","DOI":"10.1007\/s00440-016-0693-5","article-title":"Random matrices: Tail bounds for gaps between eigenvalues","volume":"167","author":"Nguyen Hoi","year":"2017","unstructured":"Hoi Nguyen, Terence Tao, and Van Vu. 2017. Random matrices: Tail bounds for gaps between eigenvalues. Probability Theory and Related Fields 167, 3\u20134 (2017), 777\u2013816.","journal-title":"Probability Theory and Related Fields"},{"key":"e_1_3_4_58_2","first-page":"568","volume-title":"STOC\u201922: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing","author":"Nie Zipei","year":"2022","unstructured":"Zipei Nie. 2022. Matrix anti-concentration inequalities with applications. In STOC\u201922: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. Stefano Leonardi and Anupam Gupta (Eds.), ACM, 568\u2013581. Retrieved fromhttps:\/\/arxiv.org\/abs\/2111.05553"},{"key":"e_1_3_4_59_2","series-title":"Lecture Notes in Computer Science","volume-title":"How to Multiply Matrices Faster","author":"Pan Victor Y.","year":"1984","unstructured":"Victor Y. Pan. 1984. How to Multiply Matrices Faster. Lecture Notes in Computer Science, Vol. 179. Springer."},{"key":"e_1_3_4_60_2","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry. An Introduction","author":"Preparata Franco P.","year":"1985","unstructured":"Franco P. Preparata and Michael Ian Shamos. 1985. Computational Geometry. An Introduction. Springer-Verlag New York."},{"issue":"4","key":"e_1_3_4_61_2","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1145\/1255443.1255449","article-title":"Sampling from large matrices: An approach through geometric functional analysis","volume":"54","author":"Rudelson Mark","year":"2007","unstructured":"Mark Rudelson and Roman Vershynin. 2007. Sampling from large matrices: An approach through geometric functional analysis. Journal of the ACM 54, 4 (2007), 21.","journal-title":"Journal of the ACM"},{"key":"e_1_3_4_62_2","first-page":"1576","volume-title":"Non-Asymptotic Theory of Random Matrices: Extreme Singular Values","author":"Rudelson Mark","year":"2010","unstructured":"Mark Rudelson and Roman Vershynin. 2010. Non-Asymptotic Theory of Random Matrices: Extreme Singular Values. World Scientific Publishing, 1576\u20131602."},{"key":"e_1_3_4_63_2","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898718003","volume-title":"Iterative Methods for Sparse Linear Systems (2nd ed.)","author":"Saad Y.","year":"2003","unstructured":"Y. Saad. 2003. Iterative Methods for Sparse Linear Systems (2nd ed.). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA. Retrieved fromhttp:\/\/www-users.cs.umn.edu\/saad\/toc.pdf"},{"issue":"2","key":"e_1_3_4_64_2","first-page":"125","article-title":"Faster algorithms via approximation theory","volume":"9","author":"Sachdeva Sushant","year":"2013","unstructured":"Sushant Sachdeva and Nisheeth K. Vishnoi. 2013. Faster algorithms via approximation theory. Theoretical Computer Science 9, 2 (2013), 125\u2013210.","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"e_1_3_4_65_2","doi-asserted-by":"crossref","first-page":"446","DOI":"10.1137\/S0895479803436202","article-title":"Smoothed analysis of the condition numbers and growth factors of matrices","volume":"28","author":"Sankar Arvind","year":"2006","unstructured":"Arvind Sankar, Daniel A. Spielman, and Shang-Hua Teng. 2006. Smoothed analysis of the condition numbers and growth factors of matrices. SIAM Journal on Matrix Analysis and Applications 28, 2 (2006), 446\u2013476.","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"key":"e_1_3_4_66_2","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1109\/FOCS.2006.37","volume-title":"Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006)","author":"Sarl\u00f3s Tam\u00e1s","year":"2006","unstructured":"Tam\u00e1s Sarl\u00f3s. 2006. Improved approximation algorithms for large matrices via random projections. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006). IEEE Computer Society, 143\u2013152."},{"key":"e_1_3_4_67_2","doi-asserted-by":"crossref","first-page":"5599","DOI":"10.1137\/1.9781611978322.192","volume-title":"Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025","author":"Shah Rikhav","year":"2025","unstructured":"Rikhav Shah. 2025. Hermitian diagonalization in linear precision. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025. Yossi Azar and Debmalya Panigrahi (Eds.), SIAM, 5599\u20135615."},{"key":"e_1_3_4_68_2","unstructured":"Jonathan R. Shewchuk. 1994. An introduction to the conjugate gradient method without the agonizing pain. Technical Report. Carnegie Mellon University USA."},{"key":"e_1_3_4_69_2","doi-asserted-by":"publisher","DOI":"10.1137\/08074489X"},{"key":"e_1_3_4_70_2","doi-asserted-by":"publisher","DOI":"10.1137\/090771430"},{"issue":"1","key":"e_1_3_4_71_2","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/s11856-011-0194-2","article-title":"An elementary proof of the restricted invertibility theorem","volume":"190","author":"Spielman Daniel A.","year":"2012","unstructured":"Daniel A. Spielman and Nikhil Srivastava. 2012. An elementary proof of the restricted invertibility theorem. Israel Journal of Mathematics 190, 1 (2012), 83\u201391. Retrieved fromhttps:\/\/arxiv.org\/pdf\/0911.1114.pdf","journal-title":"Israel Journal of Mathematics"},{"issue":"4","key":"e_1_3_4_72_2","doi-asserted-by":"crossref","first-page":"609","DOI":"10.1016\/j.jco.2005.04.002","article-title":"The shifted number system for fast linear algebra on integer matrices","volume":"21","author":"Storjohann Arne","year":"2005","unstructured":"Arne Storjohann. 2005. The shifted number system for fast linear algebra on integer matrices. Journal of Complexity 21, 4 (2005), 609\u2013650. Retrieved fromhttps:\/\/cs.uwaterloo.ca\/astorjoh\/shifted.pdf","journal-title":"Journal of Complexity"},{"issue":"4","key":"e_1_3_4_73_2","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1007\/BF02165411","article-title":"Gaussian elimination is not optimal","volume":"13","author":"Strassen Volker","year":"1969","unstructured":"Volker Strassen. 1969. Gaussian elimination is not optimal. Numerische Mathematik 13, 4 (1969), 354\u2013356.","journal-title":"Numerische Mathematik"},{"issue":"272","key":"e_1_3_4_74_2","doi-asserted-by":"crossref","first-page":"2333","DOI":"10.1090\/S0025-5718-2010-02396-8","article-title":"Smooth analysis of the condition number and the least singular value","volume":"79","author":"Tao Terence","year":"2010","unstructured":"Terence Tao and Van H. Vu. 2010. Smooth analysis of the condition number and the least singular value. Mathematics of Computation 79, 272 (2010), 2333\u20132352. Retrieved fromhttps:\/\/arxiv.org\/abs\/0805.3167","journal-title":"Mathematics of Computation"},{"issue":"1","key":"e_1_3_4_75_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1561\/2200000048","article-title":"An introduction to matrix concentration inequalities","volume":"8","author":"Tropp Joel A.","year":"2015","unstructured":"Joel A. Tropp. 2015. An introduction to matrix concentration inequalities. Foundations and Trends\u00ae in Machine Learning 8, 1\u20132 (2015), 1\u2013230.","journal-title":"Foundations and Trends\u00ae in Machine Learning"},{"issue":"1","key":"e_1_3_4_76_2","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1093\/qjmam\/1.1.287","article-title":"Rounding-off errors in matrix processes","volume":"1","author":"Turing Alan M.","year":"1948","unstructured":"Alan M. Turing. 1948. Rounding-off errors in matrix processes. The Quarterly Journal of Mechanics and Applied Mathematics 1, 1 (1948), 287\u2013308.","journal-title":"The Quarterly Journal of Mechanics and Applied Mathematics"},{"key":"e_1_3_4_77_2","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1109\/SFCS.1989.63499","volume-title":"Proceedings of the 30th Annual Symposium on Foundations of Computer Science","author":"Vaidya Pravin M.","year":"1989","unstructured":"Pravin M. Vaidya. 1989. Speeding-up linear programming using fast matrix multiplication (extended abstract). In Proceedings of the 30th Annual Symposium on Foundations of Computer Science. IEEE Computer Society, 332\u2013337."},{"key":"e_1_3_4_78_2","first-page":"887","volume-title":"Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012","author":"Williams Virginia Vassilevska","year":"2012","unstructured":"Virginia Vassilevska Williams. 2012. Multiplying matrices faster than Coppersmith-Winograd. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012. Howard J. Karloff and Toniann Pitassi (Eds.), ACM, 887\u2013898."},{"issue":"1","key":"e_1_3_4_79_2","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1109\/TIT.1986.1057137","article-title":"Solving sparse linear equations over finite fields","volume":"32","author":"Wiedemann D. H.","year":"1986","unstructured":"D. H. Wiedemann. 1986. Solving sparse linear equations over finite fields. IEEE Transactions on Information Theory 32, 1 (Jan1986), 54\u201362.","journal-title":"IEEE Transactions on Information Theory"},{"issue":"1","key":"e_1_3_4_80_2","first-page":"1","article-title":"Sketching as a tool for numerical linear algebra","volume":"10","author":"Woodruff David P.","year":"2014","unstructured":"David P. Woodruff. 2014. Sketching as a tool for numerical linear algebra. Foundations and Trends in Theoretical Computer Science 10, 1\u20132 (2014), 1\u2013157. Retrieved fromhttps:\/\/arxiv.org\/abs\/1411.4357","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"issue":"1","key":"e_1_3_4_81_2","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1137\/120895755","article-title":"Superfast and stable structured solvers for Toeplitz least squares via randomized sampling","volume":"35","author":"Xi Yuanzhe","year":"2014","unstructured":"Yuanzhe Xi, Jianlin Xia, Stephen Cauley, and Venkataramanan Balakrishnan. 2014. Superfast and stable structured solvers for Toeplitz least squares via randomized sampling. SIAM Journal on Matrix Analysis and Applications 35, 1 (2014), 44\u201372.","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"issue":"6","key":"e_1_3_4_82_2","doi-asserted-by":"crossref","first-page":"953","DOI":"10.1002\/nla.691","article-title":"Fast algorithms for hierarchically semiseparable matrices","volume":"17","author":"Xia Jianlin","year":"2010","unstructured":"Jianlin Xia, Shivkumar Chandrasekaran, Ming Gu, and Xiaoye S. Li. 2010. Fast algorithms for hierarchically semiseparable matrices. Numerical Linear Algebra with Applications 17, 6 (2010), 953\u2013976.","journal-title":"Numerical Linear Algebra with Applications"},{"issue":"3","key":"e_1_3_4_83_2","doi-asserted-by":"crossref","first-page":"837","DOI":"10.1137\/110831982","article-title":"A superfast structured solver for Toeplitz linear systems via randomized sampling","volume":"33","author":"Xia Jianlin","year":"2012","unstructured":"Jianlin Xia, Yuanzhe Xi, and Ming Gu. 2012. A superfast structured solver for Toeplitz linear systems via randomized sampling. SIAM Journal on Matrix Analysis and Applications 33, 3 (2012), 837\u2013858.","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"key":"e_1_3_4_84_2","doi-asserted-by":"crossref","unstructured":"Guo-liang Xu and Adhemar Bultheel. 1990. Matrix Pade approximation: definitions and properties. Linear Algebra and Its Applications 137-138 1 (1990) 67\u2013136.","DOI":"10.1016\/0024-3795(90)90127-X"},{"key":"e_1_3_4_85_2","volume-title":"Interior Point Algorithms: Theory and Analysis","author":"Ye Yinyu","year":"2011","unstructured":"Yinyu Ye. 2011. Interior Point Algorithms: Theory and Analysis. Vol. 44. John Wiley & Sons."},{"key":"e_1_3_4_86_2","volume-title":"Hardness and Tractability for Structured Numerical Problems","author":"Zhang Peng","year":"2018","unstructured":"Peng Zhang. 2018. Hardness and Tractability for Structured Numerical Problems. Ph.D. Dissertation. Georgia Institute of Technology. Retrieved fromhttps:\/\/arxiv.org\/abs\/1705.02944"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3767721","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,24]],"date-time":"2025-11-24T16:34:31Z","timestamp":1764002071000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3767721"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,24]]},"references-count":85,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,12,31]]}},"alternative-id":["10.1145\/3767721"],"URL":"https:\/\/doi.org\/10.1145\/3767721","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2025,11,24]]},"assertion":[{"value":"2023-07-02","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-08-08","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-11-24","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}