{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T16:30:20Z","timestamp":1759336220564,"version":"3.37.3"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,2,26]],"date-time":"2022-02-26T00:00:00Z","timestamp":1645833600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,2,26]],"date-time":"2022-02-26T00:00:00Z","timestamp":1645833600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1819166","DMS-1559587"],"award-info":[{"award-number":["DMS-1819166","DMS-1559587"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","award":["MATH+X program"],"award-info":[{"award-number":["MATH+X program"]}],"id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Corporate members of the Geo-Mathematical Imaging Group at Rice University"},{"DOI":"10.13039\/501100007185","name":"Total","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100007185","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sci Comput"],"published-print":{"date-parts":[[2022,4]]},"DOI":"10.1007\/s10915-022-01761-7","type":"journal-article","created":{"date-parts":[[2022,2,26]],"date-time":"2022-02-26T17:02:43Z","timestamp":1645894963000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Interconnected Hierarchical Structures for Fast Direct Elliptic Solution"],"prefix":"10.1007","volume":"91","author":[{"given":"Xiao","family":"Liu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianlin","family":"Xia","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maarten","family":"V. de Hoop","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaofeng","family":"Ou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,2,26]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Amestoy, P., Ashcraft, C., Boiteau, O., Buttari, A., L\u2019Excellent, J.-Y., Weisbecker, C.: Improving multifrontal methods by means of block low-rank representations. SIAM J. Sci. Comput. 37, A1451\u2013A1474 (2015)","key":"1761_CR1","DOI":"10.1137\/120903476"},{"key":"1761_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00211-002-0445-6","volume":"95","author":"M Bebendorf","year":"2003","unstructured":"Bebendorf, M., Hackbusch, W.: Existence of $$\\cal{H}$$-matrix approximants to the inverse FE-matrix of elliptic operator with $$L^{\\infty }$$-coefficients. Numer. Math. 95, 1\u201328 (2003)","journal-title":"Numer. Math."},{"key":"1761_CR3","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1017\/S0962492900002427","volume":"3","author":"TF Chan","year":"1994","unstructured":"Chan, T.F., Mathew, T.P.: Domain decomposition algorithms. Acta Numer. 3, 61\u2013143 (1994)","journal-title":"Acta Numer."},{"key":"1761_CR4","doi-asserted-by":"publisher","first-page":"2261","DOI":"10.1137\/090775932","volume":"31","author":"S Chandrasekaran","year":"2010","unstructured":"Chandrasekaran, S., Dewilde, P., Gu, M., Somasunderam, N.: On the numerical rank of the off-diagonal blocks of Schur complements of discretized elliptic PDEs. SIAM J. Matrix Anal. Appl. 31, 2261\u20132290 (2010)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"1761_CR5","doi-asserted-by":"publisher","first-page":"603","DOI":"10.1137\/S0895479803436652","volume":"28","author":"S Chandrasekaran","year":"2006","unstructured":"Chandrasekaran, S., Gu, M., Pals, T.: A fast $$ULV$$ decomposition solver for hierarchically semiseparable representations. SIAM J. Matrix Anal. Appl. 28, 603\u2013622 (2006)","journal-title":"SIAM J. Matrix Anal. Appl."},{"unstructured":"Demmel, J.W., Gilbert, J.R., Li, X.S.: SuperLU users\u2019 guide. http:\/\/crd.lbl.gov\/~xiaoye\/SuperLU\/superlu_ug.pdf","key":"1761_CR6"},{"key":"1761_CR7","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1145\/356044.356047","volume":"9","author":"IS Duff","year":"1983","unstructured":"Duff, I.S., Reid, J.K.: The multifrontal solution of indefinite sparse symmetric linear equations. ACM Trans. Math. Softw. 9, 302\u2013325 (1983)","journal-title":"ACM Trans. Math. Softw."},{"key":"1761_CR8","doi-asserted-by":"publisher","first-page":"697","DOI":"10.1002\/cpa.20358","volume":"64","author":"B Engquist","year":"2011","unstructured":"Engquist, B., Ying, L.: Sweeping preconditioner for the Helmholtz equation: hierarchical matrix representation. Commun. Pure Appl. Math. 64, 697\u2013735 (2011)","journal-title":"Commun. Pure Appl. Math."},{"key":"1761_CR9","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1137\/0710032","volume":"10","author":"A George","year":"1973","unstructured":"George, A.: Nested dissection of a regular finite element mesh. SIAM J. Numer. Anal. 10, 345\u2013363 (1973)","journal-title":"SIAM J. Numer. Anal."},{"key":"1761_CR10","doi-asserted-by":"publisher","first-page":"S358","DOI":"10.1137\/15M1010117","volume":"38","author":"P Ghysels","year":"2016","unstructured":"Ghysels, P., Li, X.S., Rouet, F.H., Williams, S., Napov, A.: An efficient multicore implementation of a novel HSS-structured multifrontal solver using randomized sampling. SIAM J. Sci. Comput. 38, S358\u2013S384 (2016)","journal-title":"SIAM J. Sci. Comput."},{"key":"1761_CR11","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/s10543-014-0499-8","volume":"55","author":"A Gillman","year":"2015","unstructured":"Gillman, A., Barnett, A.H., Martinsson, P.G.: A spectrally accurate direct solution technique for frequency-domain scattering problems with variable media. BIT Numer. Math. 55, 141\u2013170 (2015)","journal-title":"BIT Numer. Math."},{"key":"1761_CR12","doi-asserted-by":"publisher","first-page":"A2023","DOI":"10.1137\/130918988","volume":"36","author":"A Gillman","year":"2014","unstructured":"Gillman, A., Martinsson, P.G.: A direct solver with $$O(n)$$ complexity for variable coefficient elliptic PDEs discretized via a high-order composite spectral collocation method. SIAM J. Sci. Comput. 36, A2023\u2013A2046 (2014)","journal-title":"SIAM J. Sci. Comput."},{"key":"1761_CR13","doi-asserted-by":"publisher","first-page":"S61","DOI":"10.1137\/18M1194961","volume":"41","author":"C Gorman","year":"2019","unstructured":"Gorman, C., Ch\u00e1vez, G., Ghysels, P., Mary, T., Rouet, F.-H., Li, X.S.: Robust and accurate stopping criteria for adaptive randomized sampling in matrix-free hierarchically semiseparable construction. SIAM J. Sci. Comput. 41, S61\u2013S85 (2019)","journal-title":"SIAM J. Sci. Comput."},{"key":"1761_CR14","first-page":"661","volume-title":"Domain Decomposition Methods in Science and Engineering XVI","author":"L Grasedyck","year":"2006","unstructured":"Grasedyck, L., Kriemann, R., Le Borne, S.: Domain-decomposition based $$mathcal{H}$$-LU preconditioners. In: Widlund, O.B., Keyes, D.E. (eds.) Domain Decomposition Methods in Science and Engineering XVI, vol. 55, pp. 661\u2013668. Springer LNCSE, Berlin (2006)"},{"key":"1761_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00607-002-1450-4","volume":"69","author":"W Hackbusch","year":"2002","unstructured":"Hackbusch, W., B\u00f6rm, S.: Data-sparse approximation by adaptive $$\\cal{H}^{2}$$-matrices. Computing 69, 1\u201335 (2002)","journal-title":"Computing"},{"key":"1761_CR16","doi-asserted-by":"publisher","first-page":"229","DOI":"10.21136\/MB.2002.134156","volume":"127","author":"W Hackbusch","year":"2002","unstructured":"Hackbusch, W., Grasedyck, L., B\u00f6rm, S.: An introduction to hierarchical matrices. Math. Bohem. 127, 229\u2013241 (2002)","journal-title":"Math. Bohem."},{"key":"1761_CR17","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/s00791-005-0008-3","volume":"8","author":"W Hackbusch","year":"2005","unstructured":"Hackbusch, W., Khoromskij, B.N., Kriemann, R.: Direct Schur complement method by domain decomposition based on $$\\cal{H}$$-matrix approximation. Comput. Vis. Sci. 8, 179\u2013188 (2005)","journal-title":"Comput. Vis. Sci."},{"key":"1761_CR18","volume-title":"Nodal Discontinuous Galerkin Methods: Algorithms, Analysis, and Applications","author":"JS Hesthaven","year":"2007","unstructured":"Hesthaven, J.S., Warburton, T.: Nodal Discontinuous Galerkin Methods: Algorithms, Analysis, and Applications. Springer, Berlin (2007)"},{"key":"1761_CR19","doi-asserted-by":"publisher","first-page":"1415","DOI":"10.1002\/cpa.21582","volume":"69","author":"KL Ho","year":"2016","unstructured":"Ho, K.L., Ying, L.: Hierarchical interpolative factorization for elliptic operators: differential equations. Commun. Pure Appl. Math. 69, 1415\u20131451 (2016)","journal-title":"Commun. Pure Appl. Math."},{"key":"1761_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s40687-017-0100-6","volume":"4","author":"Y Li","year":"2017","unstructured":"Li, Y., Ying, L.: Distributed-memory hierarchical interpolative factorization. Res. Math. Sci. 4, 1\u201323 (2017)","journal-title":"Res. Math. Sci."},{"key":"1761_CR21","doi-asserted-by":"publisher","first-page":"4071","DOI":"10.1016\/j.jcp.2011.02.033","volume":"230","author":"L Lin","year":"2011","unstructured":"Lin, L., Lu, J., Ying, L.: Fast construction of hierarchical matrix representation from matrix\u2013vector multiplication. J. Comput. Phys. 230, 4071\u20134087 (2011)","journal-title":"J. Comput. Phys."},{"key":"1761_CR22","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1137\/1034004","volume":"34","author":"JW Liu","year":"1992","unstructured":"Liu, J.W.: The multifrontal method for sparse matrix solution: theory and practice. SIAM Rev. 34, 82\u2013109 (1992)","journal-title":"SIAM Rev."},{"key":"1761_CR23","doi-asserted-by":"publisher","first-page":"S508","DOI":"10.1137\/15M1023774","volume":"38","author":"X Liu","year":"2016","unstructured":"Liu, X., Xia, J., de Hoop, M.V.: Parallel randomized and matrix-free direct solvers for large structured dense linear systems. SIAM J. Sci. Comput. 38, S508\u2013S538 (2016)","journal-title":"SIAM J. Sci. Comput."},{"key":"1761_CR24","doi-asserted-by":"publisher","first-page":"A1174","DOI":"10.1137\/18M1224623","volume":"42","author":"X Liu","year":"2020","unstructured":"Liu, X., Xia, J., de Hoop, M.V.: Fast factorization update for general elliptic equations under multiple coefficient updates. SIAM J. Sci. Comput. 42, A1174\u2013A1199 (2020)","journal-title":"SIAM J. Sci. Comput."},{"key":"1761_CR25","doi-asserted-by":"publisher","first-page":"1251","DOI":"10.1137\/100786617","volume":"32","author":"PG Martinsson","year":"2011","unstructured":"Martinsson, P.G.: A fast randomized algorithm for computing hierarchically semiseparable representation of a matrix. SIAM. J. Matrix Anal. Appl. 32, 1251\u20131274 (2011)","journal-title":"SIAM. J. Matrix Anal. Appl."},{"key":"1761_CR26","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1016\/j.jcp.2013.02.019","volume":"242","author":"PG Martinsson","year":"2013","unstructured":"Martinsson, P.G.: A direct solver for variable coefficient elliptic PDEs discretized via a composite spectral collocation method. J. Comput. Phys. 242, 460\u2013479 (2013)","journal-title":"J. Comput. Phys."},{"key":"1761_CR27","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1137\/1003021","volume":"3","author":"S Parter","year":"1961","unstructured":"Parter, S.: The use of linear graphs in Gauss elimination. SIAM Rev. 3, 119\u2013130 (1961)","journal-title":"SIAM Rev."},{"key":"1761_CR28","doi-asserted-by":"publisher","first-page":"1104","DOI":"10.1093\/imamat\/hxx026","volume":"82","author":"M Pedneault","year":"2017","unstructured":"Pedneault, M., Catalin, T., Boubendir, Y.: Schur complement domain decomposition methods for the solution of multiple scattering problems. IMA J. Appl. Math. 82, 1104\u20131134 (2017)","journal-title":"IMA J. Appl. Math."},{"key":"1761_CR29","doi-asserted-by":"publisher","first-page":"1314","DOI":"10.1016\/j.jcp.2011.10.013","volume":"231","author":"PG Schmitz","year":"2012","unstructured":"Schmitz, P.G., Ying, L.: A fast direct solver for elliptic problems on general meshes in 2D. J. Comput. Phys. 231, 1314\u20131338 (2012)","journal-title":"J. Comput. Phys."},{"key":"1761_CR30","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/j.jcp.2013.10.030","volume":"258","author":"PG Schmitz","year":"2014","unstructured":"Schmitz, P.G., Ying, L.: A fast nested dissection solver for Cartesian 3D elliptic problems using hierarchical matrices. J. Comput. Phys. 258, 227\u2013245 (2014)","journal-title":"J. Comput. Phys."},{"key":"1761_CR31","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719574","volume-title":"Numerical Linear Algebra","author":"LN Trefethen","year":"1997","unstructured":"Trefethen, L.N., David, B.: Numerical Linear Algebra, vol. 50. SIAM, Philadelphia (1997)"},{"key":"1761_CR32","doi-asserted-by":"publisher","first-page":"8445","DOI":"10.1016\/j.jcp.2010.07.027","volume":"229","author":"S Wang","year":"2010","unstructured":"Wang, S., de Hoop, M.V., Xia, J.: Acoustic inverse scattering via Helmholtz operator factorization and optimization. J. Comput. Phys. 229, 8445\u20138462 (2010)","journal-title":"J. Comput. Phys."},{"key":"1761_CR33","doi-asserted-by":"publisher","first-page":"857","DOI":"10.1111\/j.1365-2478.2011.00982.x","volume":"59","author":"S Wang","year":"2011","unstructured":"Wang, S., de Hoop, M.V., Xia, J.: On 3D modeling of seismic wave propagation via a structured parallel multifrontal direct Helmholtz solver. Geophys. Prospect. 59, 857\u2013873 (2011)","journal-title":"Geophys. Prospect."},{"key":"1761_CR34","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1137\/120895755","volume":"35","author":"Y Xi","year":"2014","unstructured":"Xi, Y., Xia, J., Cauley, S., Balakrishnan, V.: Superfast and stable structured solvers for Toeplitz least squares via randomized sampling. SIAM J. Matrix Anal. Appl. 35, 44\u201372 (2014)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"1761_CR35","doi-asserted-by":"publisher","first-page":"974","DOI":"10.1137\/130914966","volume":"35","author":"Y Xi","year":"2014","unstructured":"Xi, Y., Xia, J., Chan, R.: A fast randomized eigensolver with structured LDL factorization update. SIAM J. Matrix Anal. Appl. 35, 974\u2013996 (2014)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"1761_CR36","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1137\/110827788","volume":"33","author":"J Xia","year":"2012","unstructured":"Xia, J.: On the complexity of some hierarchical structured matrix algorithms. SIAM J. Matrix Anal. Appl. 33, 388\u2013410 (2012)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"1761_CR37","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1137\/12087116X","volume":"34","author":"J Xia","year":"2013","unstructured":"Xia, J.: Randomized sparse direct solvers. SIAM J. Matrix Anal. Appl. 34, 197\u2013227 (2013)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"1761_CR38","doi-asserted-by":"publisher","first-page":"A832","DOI":"10.1137\/120867032","volume":"35","author":"J Xia","year":"2013","unstructured":"Xia, J.: Efficient structured multifrontal factorization for general large sparse matrices. SIAM J. Sci. Comput. 35, A832\u2013A860 (2013)","journal-title":"SIAM J. Sci. Comput."},{"key":"1761_CR39","doi-asserted-by":"publisher","first-page":"1382","DOI":"10.1137\/09074543X","volume":"31","author":"J Xia","year":"2009","unstructured":"Xia, J., Chandrasekaran, S., Gu, M., Li, X.S.: Superfast multifrontal method for large structured linear systems of equations. SIAM J. Matrix Anal. Appl. 31, 1382\u20131411 (2009)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"1761_CR40","doi-asserted-by":"publisher","first-page":"953","DOI":"10.1002\/nla.691","volume":"17","author":"J Xia","year":"2010","unstructured":"Xia, J., Chandrasekaran, S., Gu, M., Li, X.S.: Fast algorithms for hierarchically semiseparable matrices. Numer. Linear Algebra Appl. 17, 953\u2013976 (2010)","journal-title":"Numer. Linear Algebra Appl."},{"key":"1761_CR41","doi-asserted-by":"publisher","first-page":"837","DOI":"10.1137\/110831982","volume":"33","author":"J Xia","year":"2012","unstructured":"Xia, J., Xi, Y., Gu, M.: A superfast structured solver for Toeplitz linear systems via randomized sampling. SIAM J. Matrix Anal. Appl. 33, 837\u2013858 (2012)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"1761_CR42","doi-asserted-by":"publisher","first-page":"C292","DOI":"10.1137\/16M1079221","volume":"39","author":"Z Xin","year":"2017","unstructured":"Xin, Z., Xia, J., de Hoop, M.V., Cauley, S., Balakrishnan, V.: A distributed-memory randomized structured multifrontal method for sparse direct solutions. SIAM J. Sci. Comput. 39, C292\u2013C318 (2017)","journal-title":"SIAM J. Sci. Comput."}],"container-title":["Journal of Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10915-022-01761-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10915-022-01761-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10915-022-01761-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,25]],"date-time":"2022-03-25T18:28:20Z","timestamp":1648232900000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10915-022-01761-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,26]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["1761"],"URL":"https:\/\/doi.org\/10.1007\/s10915-022-01761-7","relation":{},"ISSN":["0885-7474","1573-7691"],"issn-type":[{"type":"print","value":"0885-7474"},{"type":"electronic","value":"1573-7691"}],"subject":[],"published":{"date-parts":[[2022,2,26]]},"assertion":[{"value":"18 December 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 November 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 December 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 February 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The source codes and data for the tests are available upon request. The authors declare that there is no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"15"}}