{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,23]],"date-time":"2026-10-23T23:40:48Z","timestamp":1792798848046,"version":"4.5.0"},"reference-count":57,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>We present an algorithm that on input of an $n$-vertex $m$-edge weighted graph $G$ and a value $k$ produces an incremental sparsifier $\\hat{G}$ with $n-1 + m\/k$ edges, such that the relative condition number of $G$ with $\\hat{G}$ is bounded above by $\\tilde{O}(k\\log^2 n)$, with probability $1-p$ (we use the $\\tilde{O}()$ notation to hide a factor of at most $(\\log\\log n)^4$). The algorithm runs in time $\\tilde{O}((m \\log{n} + n\\log^2{n})\\log(1\/p)).$ As a result, we obtain an algorithm that on input of an $n\\times n$ symmetric diagonally dominant matrix $A$ with $m$ nonzero entries and a vector $b$ computes a vector ${x}$ satisfying $||{x}-A^{+}b||_A&lt;\\epsilon ||A^{+}b||_A $, in expected time $\\tilde{O}(m\\log^2{n}\\log(1\/\\epsilon)).$ The solver is based on repeated applications of the incremental sparsifier that produces a chain of graphs which is then used as input to the recursive preconditioned Chebyshev iteration.<\/jats:p>","DOI":"10.1137\/110845914","type":"journal-article","created":{"date-parts":[[2014,2,20]],"date-time":"2014-02-20T12:52:01Z","timestamp":1392900721000},"page":"337-354","source":"Crossref","is-referenced-by-count":45,"title":["Approaching Optimality for Solving SDD Linear Systems"],"prefix":"10.1137","volume":"43","author":[{"given":"Ioannis","family":"Koutis","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gary L.","family":"Miller","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Richard","family":"Peng","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2014,2,20]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"I. Abraham, Y. Bartal, and O. Neiman,\n                      Nearly tight low stretch spanning trees\n                      , in Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS '08), 2008, pp. 781-790.","DOI":"10.1109\/FOCS.2008.62"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"R. Andersen, F. Chung, and K. Lang,\n                      Local graph partitioning using PageRank vectors\n                      , in Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS '06), 2006, pp. 475-486.","DOI":"10.1109\/FOCS.2006.44"},{"key":"atypb3","first-page":"395","author":"Abraham I.","year":"2012","journal-title":"New York"},{"key":"atypb4","first-page":"235","author":"Andersen R.","year":"2009","journal-title":"New York"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1109\/18.985947"},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"O. Axelsson,\n                      Iterative Solution Methods\n                      , Cambridge University Press, New York, 1994.","DOI":"10.1017\/CBO9780511624100"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"N. Alon and R. Yuster,\n                      Solving linear systems through nested dissection\n                      , in Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2010, pp. 225-234.","DOI":"10.1109\/FOCS.2010.28"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479801384019"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"G. E. Blelloch, A. Gupta, I. Koutis, G. L. Miller, R. Peng, and K. Tangwongsan,\n                      Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs\n                      , Theory Comput. Syst., 2013.","DOI":"10.1007\/s00224-013-9444-5"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479801390637"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1137\/040611781"},{"key":"atypb12","first-page":"47","author":"Bencz\u00far A. A.","year":"1996","journal-title":"New York"},{"key":"atypb13","first-page":"255","author":"Batson J. D.","year":"2009","journal-title":"New York"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"F. R. K. Chung,\n                      Spectral Graph Theory\n                      , CBMS Regional Conf. Ser. in Math. 92, AMS, Providence, RI, 1997.","DOI":"10.1090\/cbms\/092"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"P. Christiano, J. A. Kelner, A. Madry, D. Spielman, and S.H. Teng,\n                      Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs\n                      , in Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC), ACM, New York, 2011.","DOI":"10.1145\/1993636.1993674"},{"key":"atypb16","unstructured":"P. G. Doyle and J. L. Snell,\n                      Random Walks and Electric Networks\n                      , Mathematical Association of America, Washington, DC, 2000."},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1137\/050641661"},{"key":"atypb18","first-page":"71","author":"Fung W. S.","year":"2011","journal-title":"New York"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.21136\/CMJ.1973.101168"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1137\/0710032"},{"key":"atypb21","unstructured":"G. H. Golub and C. F. Van Loan,\n                      Matrix Computations\n                      , 3rd ed., The Johns Hopkins University Press, Baltimore, MD, 1996."},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"K. D. Gremban, G. L. Miller, and M. Zagha,\n                      Performance evaluation of a parallel preconditioner\n                      , in Proceedings of the 9th International Parallel Processing Symposium, IEEE, Santa Barbara, CA, 1995, pp. 65-69.","DOI":"10.1109\/IPPS.1995.395915"},{"key":"atypb23","unstructured":"K. Gremban,\n                      Combinatorial Preconditioners for Sparse, Symmetric, Diagonally Dominant Linear Systems\n                      , CMU CS Technical Report CMU-CS-96-123, Ph.D. thesis, Carnegie Mellon University, Pittsburgh, PA, 1996."},{"key":"atypb24","first-page":"246","author":"Gabow H. N.","year":"1983","journal-title":"New York"},{"key":"atypb25","unstructured":"R. Hariharan and D. Panigrahi,\n                      A Linear-Time Algorithm for Sparsification of Unweighted Graphs\n                      , preprint, CoRR, abs\/1005.0670, 2010."},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1145\/1276377.1276466"},{"key":"atypb27","unstructured":"A. Joshi,\n                      Topics in Optimization and Sparse Linear Systems\n                      , Ph.D. thesis, University of Illinois at Urbana-Champaign, 1997."},{"key":"atypb28","unstructured":"J. A. Kelner and A. Levin,\n                      Spectral sparsification in the semi-streaming setting\n                      , in Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011), T. Schwentick and C. D\u00fcrr, eds., LIPIcs. Leibniz Int. Proc. Inform. 9, Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 2011, pp. 440-451."},{"key":"atypb29","first-page":"1002","author":"Koutis I.","year":"2007","journal-title":"Philadelphia"},{"key":"atypb30","doi-asserted-by":"crossref","unstructured":"I. Koutis and G. L. Miller,\n                      Graph partitioning into isolated, high conductance clusters: Theory, computation and applications to preconditioning\n                      , in Proceedings of the 20th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2008.","DOI":"10.1145\/1378533.1378559"},{"key":"atypb31","doi-asserted-by":"crossref","unstructured":"J. A. Kelner and A. Madry,\n                      Faster generation of random spanning trees\n                      , in Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009), 2009, pp. 13-21.","DOI":"10.1109\/FOCS.2009.75"},{"key":"atypb32","doi-asserted-by":"crossref","unstructured":"I. Koutis, G. L. Miller, and R. Peng,\n                      Approaching Optimality for Solving SDD Systems\n                      , preprint, CoRR, abs\/1003.2958, 2010.","DOI":"10.1109\/FOCS.2010.29"},{"key":"atypb33","unstructured":"I. Koutis, G. L. Miller, and R. Peng,\n                      A Near-$m \\log n$ Solver for SDD Linear Systems\n                      , preprint, CoRR, abs\/1102.4842, 2011."},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1145\/2347736.2347759"},{"key":"atypb35","doi-asserted-by":"crossref","unstructured":"I. Koutis, G. L. Miller, A. Sinop, and D. Tolliver,\n                      Combinatorial Preconditioners and Multilevel Solvers for Problems in Computer Vision and Image Processing\n                      , Technical report, CMU, 2009.","DOI":"10.1007\/978-3-642-10331-5_99"},{"key":"atypb36","first-page":"57","author":"Kolla A.","year":"2010","journal-title":"New York"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1016\/j.cviu.2011.05.013"},{"key":"atypb38","first-page":"911","author":"Kelner J. A.","year":"2013","journal-title":"New York"},{"key":"atypb39","first-page":"755","author":"Lee Y. T.","year":"2013","journal-title":"New York"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1137\/0716027"},{"key":"atypb41","doi-asserted-by":"crossref","unstructured":"Y. T. Lee and A. Sidford,\n                      Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems\n                      , preprint, CoRR, abs\/1305.1922, 2013.","DOI":"10.1109\/FOCS.2013.24"},{"key":"atypb42","doi-asserted-by":"crossref","unstructured":"A. Madry,\n                      Navigating Central Path with Electrical Flows: From Flows to Matchings, and Back\n                      , preprint, CoRR, abs\/1307.2205, 2013.","DOI":"10.1109\/FOCS.2013.35"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1145\/1360612.1360692"},{"key":"atypb44","unstructured":"G. Royle and C. Godsil,\n                      Algebraic Graph Theory\n                      , Grad. Texts in Math., Springer, New York, 1997."},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1145\/1255443.1255449"},{"key":"atypb46","unstructured":"D. A. Spielman and S. I. Daitch,\n                      Faster approximate lossy generalized flow via interior point algorithms\n                      , in Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 2008."},{"key":"atypb47","unstructured":"D. A. Spielman,\n                      Algorithms, graph theory, and linear equations in Laplacian matrices\n                      , in Proceedings of the International Congress of Mathematicians, 2010."},{"key":"atypb48","first-page":"563","author":"Spielman D. A.","year":"2008","journal-title":"New York"},{"key":"atypb49","doi-asserted-by":"crossref","unstructured":"D. A. Spielman and S.H. Teng,\n                      Spectral partitioning works: Planar graphs and finite element meshes\n                      , in Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1996, pp. 96-105.","DOI":"10.1109\/SFCS.1996.548468"},{"key":"atypb50","doi-asserted-by":"crossref","unstructured":"D. A. Spielman and S.H. Teng,\n                      Solving sparse, symmetric, diagonally-dominant linear systems in time $O$($m^{1.31}$)\n                      , in Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2003, pp. 416-427.","DOI":"10.1109\/SFCS.2003.1238215"},{"key":"atypb51","first-page":"81","author":"Spielman D. A.","year":"2004","journal-title":"New York"},{"key":"atypb52","unstructured":"D. A. Spielman and S.H. Teng,\n                      Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems\n                      , preprint, CoRR, abs\/cs\/0607105, 2006."},{"key":"atypb53","unstructured":"D. A. Spielman and S.H. Teng,\n                      Spectral Sparsification of Graphs\n                      , preprint, CoRR, abs\/ 0808.4134, 2008."},{"key":"atypb54","doi-asserted-by":"publisher","DOI":"10.1145\/322154.322161"},{"key":"atypb55","first-page":"2","author":"Teng S.-H.","year":"2010","journal-title":"Berlin"},{"key":"atypb56","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-011-9099-z"},{"key":"atypb57","unstructured":"P. M. Vaidya,\n                      Solving Linear Equations with Symmetric Diagonally Dominant Matrices by Constructing Good Preconditioners\n                      , manuscript; a talk based on this manuscript was presented at the IMA Workshop on Graph Theory and Sparse Matrix Computation, 1991."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/110845914","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:00:14Z","timestamp":1787338814000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/110845914"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":57,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1137\/110845914"],"URL":"https:\/\/doi.org\/10.1137\/110845914","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1]]}}}