{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T14:44:34Z","timestamp":1787496274884,"version":"build-2736575974"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"10","license":[{"start":{"date-parts":[[2012,10,1]],"date-time":"2012-10-01T00:00:00Z","timestamp":1349049600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100006112","name":"Microsoft Research","doi-asserted-by":"publisher","award":["CCF-1018463CCF-1149048ASP@Microsoft Research Fellowship"],"award-info":[{"award-number":["CCF-1018463CCF-1149048ASP@Microsoft Research Fellowship"]}],"id":[{"id":"10.13039\/100006112","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-1018463CCF-1149048ASP@Microsoft Research Fellowship"],"award-info":[{"award-number":["CCF-1018463CCF-1149048ASP@Microsoft Research Fellowship"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Commun. ACM"],"published-print":{"date-parts":[[2012,10]]},"abstract":"<jats:p>The solution of linear systems is a problem of fundamental theoretical importance but also one with a myriad of applications in numerical mathematics, engineering, and science. Linear systems that are generated by real-world applications frequently fall into special classes. Recent research led to a fast algorithm for solving symmetric diagonally dominant (SDD) linear systems. We give an overview of this solver and survey the underlying notions and tools from algebra, probability, and graph algorithms. We also discuss some of the many and diverse applications of SDD solvers.<\/jats:p>","DOI":"10.1145\/2347736.2347759","type":"journal-article","created":{"date-parts":[[2012,9,25]],"date-time":"2012-09-25T19:48:08Z","timestamp":1348602488000},"page":"99-107","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":22,"title":["A fast solver for a class of linear systems"],"prefix":"10.1145","volume":"55","author":[{"given":"Ioannis","family":"Koutis","sequence":"first","affiliation":[{"name":"University of Puerto Rico-Rio Piedras"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gary L.","family":"Miller","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Richard","family":"Peng","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2012,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214015"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792224474"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989493.1989496"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/040611781"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993674"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060665"},{"key":"e_1_2_1_7_1","volume-title":"Proc. 18th ACM--SIAM Symposium on Discrete Algorithms (SODA)","author":"Koutis I.","year":"2007","unstructured":"Koutis , I. , Miller , G.L. A linear work, O(n 1\/6) time, parallel algorithm for solving planar Laplacians . In Proc. 18th ACM--SIAM Symposium on Discrete Algorithms (SODA) , 2007 . Koutis, I., Miller, G.L. A linear work, O(n 1\/6) time, parallel algorithm for solving planar Laplacians. In Proc. 18th ACM--SIAM Symposium on Discrete Algorithms (SODA), 2007."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1378533.1378559"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.29"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.85"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cviu.2011.05.013"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2070781.2024211"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1002\/asi.v58:7"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pcbi.1000350"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1255443.1255449"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.66"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374441"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374456"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007372"},{"key":"e_1_2_1_20_1","volume-title":"Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. CoRR, abs\/cs\/0607105","author":"Spielman D.A.","year":"2006","unstructured":"Spielman , D.A. , Teng , S.-H. Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. CoRR, abs\/cs\/0607105 , 2006 . Spielman, D.A., Teng, S.-H. Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. CoRR, abs\/cs\/0607105, 2006."},{"key":"e_1_2_1_21_1","volume-title":"ARVO Annual Meeting","author":"Tolliver D.A.","year":"2008","unstructured":"Tolliver , D.A. , Koutis , I. , Ishikawa , H. , Schuman , J.S. , Miller , G.L. Automatic multiple retinal layer segmentation in spectral domain oct scans via spectral rounding . In ARVO Annual Meeting , May 2008 . Tolliver, D.A., Koutis, I., Ishikawa, H., Schuman, J.S., Miller, G.L. Automatic multiple retinal layer segmentation in spectral domain oct scans via spectral rounding. In ARVO Annual Meeting, May 2008."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/374106"},{"key":"e_1_2_1_23_1","volume-title":"October","author":"Vaidya P.M.","year":"1991","unstructured":"Vaidya , P.M. Solving linear equations with symmetric diagonally dominant matrices by constructing good preconditioners. A Talk Based on this Manuscript was Presented at the IMA Workshop on Graph Theory and Sparse Matrix Computation , October 1991 . Vaidya, P.M. Solving linear equations with symmetric diagonally dominant matrices by constructing good preconditioners. A Talk Based on this Manuscript was Presented at the IMA Workshop on Graph Theory and Sparse Matrix Computation, October 1991."},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 44th Symposium on Theory of Computing, STOC '12","author":"Vassilevska Williams V.","year":"2012","unstructured":"Vassilevska Williams , V. Breaking the Coppersmith-Winograd barrier . In Proceedings of the 44th Symposium on Theory of Computing, STOC '12 , 2012 . Vassilevska Williams, V. Breaking the Coppersmith-Winograd barrier. In Proceedings of the 44th Symposium on Theory of Computing, STOC '12, 2012."}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2347736.2347759","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2347736.2347759","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:05:58Z","timestamp":1750230358000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2347736.2347759"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,10]]},"references-count":24,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2012,10]]}},"alternative-id":["10.1145\/2347736.2347759"],"URL":"https:\/\/doi.org\/10.1145\/2347736.2347759","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"value":"0001-0782","type":"print"},{"value":"1557-7317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,10]]},"assertion":[{"value":"2012-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}