{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,27]],"date-time":"2026-09-27T08:38:55Z","timestamp":1790498335388,"version":"4.1.0"},"reference-count":58,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/100001491","name":"Belgian American Educational Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100001491","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006754","name":"Army Research Laboratory","doi-asserted-by":"publisher","award":["W911NF-07-2-0027"],"award-info":[{"award-number":["W911NF-07-2-0027"]}],"id":[{"id":"10.13039\/100006754","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003130","name":"Fonds Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003130","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2017,1]]},"abstract":"<jats:p>Inversion of sparse matrices with standard direct solve schemes is robust but computationally expensive. Iterative solvers, on the other hand, demonstrate better scalability but need to be used with an appropriate preconditioner (e.g., ILU, AMG, Gauss--Seidel) for proper convergence. The choice of an effective preconditioner is highly problem dependent. We propose a novel fully algebraic sparse matrix solve algorithm. The computational complexity is linear under the assumption that fill-in blocks have bounded rank. Our scheme is based on the Gauss elimination. For a given matrix, we approximate the LU factorization with a tunable accuracy determined a priori. This method can be used as a stand-alone direct solver, or it can be used as a black-box preconditioner in conjunction with iterative methods such as GMRES. The proposed solver is based on the low-rank approximation of fill-ins generated during the elimination. Similar to $\\mathcal{H}$-matrices, fill-ins corresponding to blocks that are well-separated in the adjacency graph are represented via a hierarchical structure. The linear complexity of the algorithm is guaranteed if the blocks corresponding to well-separated clusters of variables are numerically low-rank.<\/jats:p>","DOI":"10.1137\/15m1046939","type":"journal-article","created":{"date-parts":[[2017,5,23]],"date-time":"2017-05-23T11:55:26Z","timestamp":1495540526000},"page":"A797-A830","source":"Crossref","is-referenced-by-count":32,"title":["Fast Hierarchical Solvers For Sparse Matrices Using Extended Sparsification and Low-Rank Approximation"],"prefix":"10.1137","volume":"39","author":[{"given":"Hadi","family":"Pouransari","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pieter","family":"Coulier","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eric","family":"Darve","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2017,5,23]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.28"},{"key":"atypb2","unstructured":"S. Ambikasaran,\n                      Fast Algorithms for Dense Numerical Linear Algebra and Applications\n                      , Ph.D. thesis, Stanford University, Stanford, CA, 2013."},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-013-9714-z"},{"key":"atypb4","volume-title":"The Inverse Fast Multipole Method, preprint, arXiv:1407.1572","author":"Ambikasaran S.","year":"2014"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2015.10.012"},{"key":"atypb6","volume-title":"Tools","author":"Anderson E.","year":"1999"},{"key":"atypb7","unstructured":"M. Bebendorf,\n                      Hierarchical Matrices\n                      , Springer, New York, 2008."},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1007\/s00607-002-1469-6"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/S0955-7997(02)00152-2"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/0096-3003(86)90095-0"},{"key":"atypb11","first-page":"257","volume-title":"Sparsity and Its Applications","author":"Brandt A.","year":"1985"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1974-0331751-8"},{"key":"atypb13","first-page":"67","volume":"88","author":"Chan Tony F","year":"1987","journal-title":"Linear Algebra Appl."},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1137\/050639028"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479803436652"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1006\/jcph.1993.1069"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28396"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2014.04.002"},{"key":"atypb19","volume-title":"The Inverse Fast Multipole Method: Using a Fast Approximate Direct Solver as a Preconditioner for Dense Linear Systems, preprint, arXiv:1508.01835","author":"Coulier P.","year":"2015"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1006\/jcph.2000.6451"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718881"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2009.08.031"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1137\/0710032"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1002\/nme.2595"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1137\/130918988"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1007\/s11464-012-0188-3"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492906410011"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9991(87)90140-9"},{"key":"atypb29","unstructured":"G. Guennebaud and B. Jacob, et al.\n                      Eigen v\n                      3,http:\/\/eigen.tuxfamily.org(2010)."},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1016\/S0045-7930(98)00017-6"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1007\/s006070050015"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-9274(02)00121-6"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-0427(00)00486-6"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1137\/0905023"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1137\/090771806"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.6028\/jres.049.044"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479899356080"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.21582"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.21577"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(82)90007-4"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2011.01.008"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1137\/120872735"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1137\/0716027"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1002\/nla.2006"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1115\/1.1482087"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1137\/110833142"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1137\/0712047"},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-61142-8_588"},{"key":"atypb49","doi-asserted-by":"publisher","DOI":"10.1137\/140962681"},{"key":"atypb50","first-page":"43","volume-title":"Ann. Res. Briefs","author":"Pouransari H.","year":"2015"},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611971057.ch4"},{"key":"atypb52","doi-asserted-by":"publisher","DOI":"10.1002\/nla.1680010405"},{"key":"atypb53","doi-asserted-by":"publisher","DOI":"10.1137\/0907058"},{"key":"atypb54","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-0427(00)00516-1"},{"key":"atypb55","volume-title":"A Randomized Blocked Algorithm for Efficiently Computing Rank-Revealing Factorizations of Matrices, preprint, arXiv:1503.07157","author":"Voronin S.","year":"2015"},{"key":"atypb56","doi-asserted-by":"publisher","DOI":"10.1002\/nla.691"},{"key":"atypb57","doi-asserted-by":"publisher","DOI":"10.1137\/0602010"},{"key":"atypb58","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2003.11.021"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/15M1046939","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:41:53Z","timestamp":1787326913000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/15M1046939"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1]]},"references-count":58,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["10.1137\/15M1046939"],"URL":"https:\/\/doi.org\/10.1137\/15m1046939","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,1]]}}}