{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T17:18:41Z","timestamp":1781630321898,"version":"3.54.5"},"publisher-location":"New York, NY, USA","reference-count":28,"publisher":"ACM","license":[{"start":{"date-parts":[[2017,6,19]],"date-time":"2017-06-19T00:00:00Z","timestamp":1497830400000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1111257"],"award-info":[{"award-number":["CCF-1111257"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-12-1-0175"],"award-info":[{"award-number":["FA9550-12-1-0175"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","award":["Simons Investigator Award to Daniel A. Spielman"],"award-info":[{"award-number":["Simons Investigator Award to Daniel A. Spielman"]}],"id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2016,6,19]]},"DOI":"10.1145\/2897518.2897640","type":"proceedings-article","created":{"date-parts":[[2016,6,10]],"date-time":"2016-06-10T09:04:07Z","timestamp":1465549447000},"page":"842-850","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":53,"title":["Sparsified Cholesky and multigrid solvers for connection laplacians"],"prefix":"10.1145","author":[{"given":"Rasmus","family":"Kyng","sequence":"first","affiliation":[{"name":"Yale University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yin Tat","family":"Lee","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Richard","family":"Peng","sequence":"additional","affiliation":[{"name":"Georgia Tech, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sushant","family":"Sachdeva","sequence":"additional","affiliation":[{"name":"Yale University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel A.","family":"Spielman","sequence":"additional","affiliation":[{"name":"Yale University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,6,19]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/12089939X"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/3DIMPVT.2012.46"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/120875338"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479801384019"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591833"},{"key":"e_1_3_2_1_6_1","volume-title":"Uniform sampling for matrix approximation. arXiv preprint arXiv:1408.5099","author":"Cohen M. B.","year":"2014","unstructured":"M. B. Cohen, Y. T. Lee, C. Musco, C. Musco, R. Peng, and A. Sidford. Uniform sampling for matrix approximation. arXiv preprint arXiv:1408.5099, 2014."},{"key":"e_1_3_2_1_7_1","volume-title":"Sparse sums of positive semidefinite matrices. CoRR, abs\/1107.0088","author":"de Carli Silva M. K.","year":"2011","unstructured":"M. K. de Carli Silva, N. J. A. Harvey, and C. M. Sato. Sparse sums of positive semidefinite matrices. CoRR, abs\/1107.0088, 2011."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488724"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.29"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.85"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461992"},{"key":"e_1_3_2_1_12_1","volume-title":"Sparsified cholesky and multigrid solvers for connection laplacians. CoRR, abs\/1512.01892","author":"Kyng R.","year":"2015","unstructured":"R. Kyng, Y. T. Lee, R. Peng, S. Sachdeva, and D. A. Spielman. Sparsified cholesky and multigrid solvers for connection laplacians. CoRR, abs\/1512.01892, 2015."},{"key":"e_1_3_2_1_13_1","volume-title":"Sparsified cholesky solvers for SDD linear systems. CoRR, abs\/1506.08204","author":"Lee Y. T.","year":"2015","unstructured":"Y. T. Lee, R. Peng, and D. A. Spielman. Sparsified cholesky solvers for SDD linear systems. CoRR, abs\/1506.08204, 2015."},{"key":"e_1_3_2_1_14_1","volume-title":"Alternating projection, ptychographic imaging and phase synchronization. arXiv preprint arXiv:1402.0550","author":"Marchesini S.","year":"2014","unstructured":"S. Marchesini, Y.-C. Tu, and H.-t. Wu. Alternating projection, ptychographic imaging and phase synchronization. arXiv preprint arXiv:1402.0550, 2014."},{"issue":"137","key":"e_1_3_2_1_15_1","first-page":"148","article-title":"An iterative solution method for linear systems of which the coefficient matrix is a symmetric m-matrix","volume":"31","author":"Meijerink J. A.","year":"1977","unstructured":"J. A. Meijerink and H. A. v. d. Vorst. An iterative solution method for linear systems of which the coefficient matrix is a symmetric m-matrix. Mathematics of Computation, 31(137):148\u2013162, 1977.","journal-title":"Mathematics of Computation"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133078"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/140977576"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591832"},{"key":"e_1_3_2_1_19_1","series-title":"SIAM journal on imaging sciences, 5(3):1088\u20131110","volume-title":"Viewing direction estimation in cryo-em using synchronization","author":"Shkolnisky Y.","year":"2012","unstructured":"Y. Shkolnisky and A. Singer. Viewing direction estimation in cryo-em using synchronization. SIAM journal on imaging sciences, 5(3):1088\u20131110, 2012."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/090767777"},{"key":"e_1_3_2_1_21_1","volume-title":"Vector diffusion maps and the connection laplacian. Communications on pure and applied mathematics, 65(8)","author":"Singer A.","year":"2012","unstructured":"A. Singer and H.-T. Wu. Vector diffusion maps and the connection laplacian. Communications on pure and applied mathematics, 65(8), 2012."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/080734029"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/080744888"},{"key":"e_1_3_2_1_24_1","first-page":"835","article-title":"Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. SIAM. J. Matrix Anal. &","volume":"35","author":"Spielman D. A.","year":"2014","unstructured":"D. A. Spielman and S.-H. Teng. Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. SIAM. J. Matrix Anal. & Appl., 35:835\u02c6 a \u02d8 A\u00b8 S885, 2014.","journal-title":"Appl."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/374106"},{"key":"e_1_3_2_1_26_1","volume-title":"Solving linear equations with symmetric diagonally dominant matrices by constructing good preconditioners. Unpublished manuscript UIUC","author":"Vaidya P. M.","year":"1990","unstructured":"P. M. Vaidya. Solving linear equations with symmetric diagonally dominant matrices by constructing good preconditioners. Unpublished manuscript UIUC 1990."},{"key":"e_1_3_2_1_27_1","volume-title":"Minneapolis.","author":"A","year":"1990","unstructured":"A talk based on the manuscript was presented at the IMA Workshop on Graph Theory and Sparse Matrix Computation, October 1991, Minneapolis., 1990."},{"key":"e_1_3_2_1_28_1","volume-title":"Rotationally invariant image representation for viewing direction classification in cryo-em. Journal of structural biology, 186(1):153\u2013166","author":"Zhao Z.","year":"2014","unstructured":"Z. Zhao and A. Singer. Rotationally invariant image representation for viewing direction classification in cryo-em. Journal of structural biology, 186(1):153\u2013166, 2014."}],"event":{"name":"STOC '16: Symposium on Theory of Computing","location":"Cambridge MA USA","acronym":"STOC '16","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the forty-eighth annual ACM symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2897518.2897640","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2897518.2897640","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2897518.2897640","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:40:55Z","timestamp":1763458855000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2897518.2897640"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,19]]},"references-count":28,"alternative-id":["10.1145\/2897518.2897640","10.1145\/2897518"],"URL":"https:\/\/doi.org\/10.1145\/2897518.2897640","relation":{},"subject":[],"published":{"date-parts":[[2016,6,19]]},"assertion":[{"value":"2016-06-19","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}