{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T15:49:01Z","timestamp":1778860141527,"version":"3.51.4"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T00:00:00Z","timestamp":1648771200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T00:00:00Z","timestamp":1648771200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000104","name":"National Aeronautics and Space Administration","doi-asserted-by":"publisher","award":["80NSSC18M0152"],"award-info":[{"award-number":["80NSSC18M0152"]}],"id":[{"id":"10.13039\/100000104","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006234","name":"Sandia National Laboratories","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006234","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,5]]},"DOI":"10.1007\/s10915-022-01824-9","type":"journal-article","created":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T10:33:10Z","timestamp":1648809190000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Hierarchical Orthogonal Factorization: Sparse Least Squares Problems"],"prefix":"10.1007","volume":"91","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7088-9261","authenticated-orcid":false,"given":"Abeynaya","family":"Gnanasekaran","sequence":"first","affiliation":[]},{"given":"Eric","family":"Darve","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,4,1]]},"reference":[{"key":"1824_CR1","doi-asserted-by":"crossref","unstructured":"Amestoy, P.R., Duff, I.S., L\u2019Excellent, J.Y., Koster, J.: Mumps: a general purpose distributed memory sparse solver. In: S\u00f8revik, T., Manne, F., Gebremedhin, A.H., Moe, R. (eds.) Applied Parallel Computing. New Paradigms for HPC in Industry and Academia, pp. 121\u2013130. Springer Berlin Heidelberg, Berlin, Heidelberg (2001)","DOI":"10.1007\/3-540-70734-4_16"},{"key":"1824_CR2","doi-asserted-by":"publisher","unstructured":"Benner, P., Mach, T.: On the qr decomposition of h-matrices. Computing 88 (2010). https:\/\/doi.org\/10.1007\/s00607-010-0087-y","DOI":"10.1007\/s00607-010-0087-y"},{"issue":"2","key":"1824_CR3","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1137\/S106482750240649X","volume":"25","author":"M Benzi","year":"2003","unstructured":"Benzi, M., T\u016fma, M.: A robust preconditioner with low memory requirements for large sparse least squares problems. SIAM J. Sci. Comput. 25(2), 499\u2013512 (2003)","journal-title":"SIAM J. Sci. Comput."},{"key":"1824_CR4","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/0024-3795(87)90101-7","volume":"88\u201389","author":"A Bjorck","year":"1987","unstructured":"Bjorck, A.: Stability analysis of the method of semi-normal equations for least squares problems. Linear Algebra Appl. 88\u201389, 31\u201348 (1987). https:\/\/doi.org\/10.1016\/0024-3795(87)90101-7","journal-title":"Linear Algebra Appl."},{"key":"1824_CR5","doi-asserted-by":"crossref","unstructured":"Bjorck, A.: Numerical methods for least squares problems. SIAM, Philadelphia, PA (1996). https:\/\/cds.cern.ch\/record\/1411947","DOI":"10.1137\/1.9781611971484"},{"key":"1824_CR6","doi-asserted-by":"publisher","first-page":"715","DOI":"10.1137\/19M123806X","volume":"41","author":"L Cambier","year":"2020","unstructured":"Cambier, L., Chen, C., Boman, E., Rajamanickam, S., Tuminaro, R., Darve, E.: An algebraic sparsified nested dissection algorithm using low-rank approximations. SIAM J. Matrix Anal. Appl. 41, 715\u2013746 (2020). https:\/\/doi.org\/10.1137\/19M123806X","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"1824_CR7","unstructured":"\u00c7ataly\u00fcrek, \u00dc.V., Aykanat, C.: Patoh (partitioning tool for hypergraphs). In: Encyclopedia of Parallel Computing (2011)"},{"key":"1824_CR8","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1016\/S0377-0427(97)00171-4","volume":"86","author":"E Chow","year":"1997","unstructured":"Chow, E., Saad, Y.: Experimental study of ilu preconditioners for indefinite matrices. J. Comput. Appl. Math. 86, 387\u2013414 (1997)","journal-title":"J. Comput. Appl. Math."},{"key":"1824_CR9","doi-asserted-by":"publisher","unstructured":"Davis, T.A., Hu, Y.: The university of florida sparse matrix collection. ACM Trans. Math. Softw. 38(1) (2011). https:\/\/doi.org\/10.1145\/2049662.2049663","DOI":"10.1145\/2049662.2049663"},{"key":"1824_CR10","doi-asserted-by":"publisher","unstructured":"Devine, K.D., Boman, E.G., Heaphy, R.T., Bisseling, R.H., Catalyurek, U.V.: Parallel hypergraph partitioning for scientific computing. In: Proceedings 20th IEEE International Parallel Distributed Processing Symposium, p. 10 (2006). https:\/\/doi.org\/10.1109\/IPDPS.2006.1639359","DOI":"10.1109\/IPDPS.2006.1639359"},{"issue":"3","key":"1824_CR11","doi-asserted-by":"publisher","first-page":"A1809","DOI":"10.1137\/19m1238265","volume":"42","author":"R Estrin","year":"2020","unstructured":"Estrin, R., Friedlander, M.P., Orban, D., Saunders, M.A.: Implementing a smooth exact penalty function for equality-constrained nonlinear optimization. SIAM J. Sci. Comput. 42(3), A1809\u2013A1835 (2020). https:\/\/doi.org\/10.1137\/19m1238265","journal-title":"SIAM J. Sci. Comput."},{"key":"1824_CR12","unstructured":"Faverge, M., Pichon, G., Ramet, P., Roman, J.: On the use of h-matrix arithmetic in pastix: a preliminary study. In: Workshop on Fast Solvers. Toulouse, France (2015). http:\/\/www.labri.fr\/~ramet\/restricted\/cimi15.pdf"},{"key":"1824_CR13","doi-asserted-by":"publisher","first-page":"91","DOI":"10.4310\/CMS.2020.v18.n1.a4","volume":"18","author":"J Feliu-Fab\u00e0","year":"2020","unstructured":"Feliu-Fab\u00e0, J., Ho, K., Ying, L.: Recursively preconditioned hierarchical interpolative factorization for elliptic partial differential equations. Commun. Math. Sci. 18, 91\u2013108 (2020). https:\/\/doi.org\/10.4310\/CMS.2020.v18.n1.a4","journal-title":"Commun. Math. Sci."},{"key":"1824_CR14","doi-asserted-by":"publisher","unstructured":"Feliu-Fab\u00e0, J., Ying, L.: Hierarchical interpolative factorization preconditioner for parabolic equations. J. Sci. Comput. 85 (2020). https:\/\/doi.org\/10.1007\/s10915-020-01343-5","DOI":"10.1007\/s10915-020-01343-5"},{"key":"1824_CR15","doi-asserted-by":"crossref","unstructured":"Fong, D.C.L., Saunders, M.A.: Lsmr: an iterative algorithm for sparse least-squares problems. SIAM J. Sci. Comput. 33(5), 2950\u20132971 (2011). http:\/\/dblp.uni-trier.de\/db\/journals\/siamsc\/siamsc33.html#FongS11","DOI":"10.1137\/10079687X"},{"issue":"2","key":"1824_CR16","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(2), 345\u2013363 (1973). https:\/\/doi.org\/10.1137\/0710032","journal-title":"SIAM J. Numer. Anal."},{"issue":"5","key":"1824_CR17","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(5), S358\u2013S384 (2016)","journal-title":"SIAM J. Sci. Comput."},{"key":"1824_CR18","doi-asserted-by":"publisher","unstructured":"Gnanasekaran, A., Darve, E.: A fast sparse qr factorization for solving linear least squares problems in graphics. In: ACM SIGGRAPH 2021 Talks, pp. 1\u20132 (2021). https:\/\/doi.org\/10.1145\/3450623.3464639","DOI":"10.1145\/3450623.3464639"},{"issue":"1","key":"1824_CR19","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1137\/20M1373475","volume":"43","author":"A Gnanasekaran","year":"2022","unstructured":"Gnanasekaran, A., Darve, E.: Hierarchical orthogonal factorization: Sparse square matrices. SIAM J. Matrix Anal. Appl. 43(1), 94\u2013123 (2022)","journal-title":"SIAM J. Matrix Anal. Appl."},{"issue":"3","key":"1824_CR20","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1007\/BF01436075","volume":"7","author":"G Golub","year":"1965","unstructured":"Golub, G.: Numerical methods for solving linear least squares problems. Numer. Math. 7(3), 206\u2013216 (1965). https:\/\/doi.org\/10.1007\/BF01436075","journal-title":"Numer. Math."},{"key":"1824_CR21","volume-title":"Matrix Computations","author":"GH Golub","year":"1996","unstructured":"Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. Johns Hopkins University Press, USA (1996)","edition":"3"},{"issue":"2","key":"1824_CR22","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1006\/jcph.1997.5706","volume":"135","author":"L Greengard","year":"1997","unstructured":"Greengard, L., Rokhlin, V.: A fast algorithm for particle simulations. J. Comput. Phys. 135(2), 280\u2013292 (1997). https:\/\/doi.org\/10.1006\/jcph.1997.5706","journal-title":"J. Comput. Phys."},{"key":"1824_CR23","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1017\/S0962492900002725","volume":"6","author":"L Greengard","year":"1997","unstructured":"Greengard, L., Rokhlin, V.: A new version of the fast multipole method for the laplace equation in three dimensions. Acta Numer. 6, 229\u2013269 (1997). https:\/\/doi.org\/10.1017\/S0962492900002725","journal-title":"Acta Numer."},{"key":"1824_CR24","doi-asserted-by":"publisher","first-page":"409","DOI":"10.6028\/jres.049.044","volume":"49","author":"MR Hestenes","year":"1952","unstructured":"Hestenes, M.R., Stiefel, E.: Methods of conjugate gradients for solving linear systems. J. Res. Natl. Bur. Stand. 49, 409\u2013436 (1952)","journal-title":"J. Res. Natl. Bur. Stand."},{"key":"1824_CR25","doi-asserted-by":"publisher","unstructured":"Ho, K., Ying, L.: Hierarchical interpolative factorization for elliptic operators: integral equations. Commun. Pure Appl. Math. 69 (2013). https:\/\/doi.org\/10.1002\/cpa.21577","DOI":"10.1002\/cpa.21577"},{"key":"1824_CR26","doi-asserted-by":"publisher","first-page":"1415","DOI":"10.1002\/cpa.21582","volume":"69","author":"KL Ho","year":"2013","unstructured":"Ho, K.L., Ying, L.: Hierarchical interpolative factorization for elliptic operators: differential equations. Commun. Pure Appl. Math. 69, 1415\u20131451 (2013)","journal-title":"Commun. Pure Appl. Math."},{"key":"1824_CR27","unstructured":"HSL.: A collection of fortran codes for large scale scientific Computation (2013). http:\/\/www.hsl.rl.ac.uk"},{"key":"1824_CR28","unstructured":"James, D.: Conjugate gradient methods for constrained least squares problems. Ph.D. thesis, Dept. of Math., North Carolina State University (1990)"},{"issue":"4","key":"1824_CR29","doi-asserted-by":"publisher","first-page":"978","DOI":"10.1137\/0905067","volume":"5","author":"A Jennings","year":"1984","unstructured":"Jennings, A., Ajiz, M.A.: Incomplete methods for solving $$a^t ax = b$$. SIAM J. Sci. Stat. Comput. 5(4), 978\u2013987 (1984). https:\/\/doi.org\/10.1137\/0905067","journal-title":"SIAM J. Sci. Stat. Comput."},{"issue":"1","key":"1824_CR30","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1137\/S1064827595287997","volume":"20","author":"G Karypis","year":"1998","unstructured":"Karypis, G., Kumar, V.: A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20(1), 359\u2013392 (1998)","journal-title":"SIAM J. Sci. Comput."},{"key":"1824_CR31","doi-asserted-by":"crossref","unstructured":"Karypis, G., Kumar, V.: Hmetis: a hypergraph partitioning package (1998)","DOI":"10.1145\/266021.266273"},{"key":"1824_CR32","unstructured":"Klockiewicz, B., Cambier, L., Humble, R., Tchelepi, H., Darve, E.: Second order accurate hierarchical approximate factorization of sparse spd matrices. arXiv preprint arXiv:2007.00789 (2020)"},{"key":"1824_CR33","doi-asserted-by":"publisher","first-page":"524","DOI":"10.1137\/050633032","volume":"28","author":"N Li","year":"2006","unstructured":"Li, N., Saad, Y.: Miqr: a multilevel incomplete qr preconditioner for large sparse least squares problems. SIAM J. Matrix Anal. Appl. 28, 524\u2013550 (2006). https:\/\/doi.org\/10.1137\/050633032","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"1824_CR34","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1090\/S0025-5718-1980-0559197-0","volume":"34","author":"T Manteuffel","year":"1980","unstructured":"Manteuffel, T.: An incomplete factorization technique for positive definite linear systems. Math. Comput. 34, 473\u2013497 (1980)","journal-title":"Math. Comput."},{"issue":"1","key":"1824_CR35","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/110828472","volume":"34","author":"K Morikuni","year":"2013","unstructured":"Morikuni, K., Hayami, K.: Inner-iteration krylov subspace methods for least squares problems. SIAM J. Matrix Anal. Appl. 34(1), 1\u201322 (2013)","journal-title":"SIAM J. Matrix Anal. Appl."},{"issue":"1","key":"1824_CR36","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/130946009","volume":"36","author":"K Morikuni","year":"2015","unstructured":"Morikuni, K., Hayami, K.: Convergence of inner-iteration gmres methods for rank-deficient least squares problems. SIAM J. Matrix Anal. Appl. 36(1), 225\u2013250 (2015)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"1824_CR37","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1109\/MAP.2014.6931698","volume":"56","author":"J Nagel","year":"2014","unstructured":"Nagel, J.: Numerical solutions to poisson equations using the finite-difference method [education column]. IEEE Antennas Propag. Mag. 56, 209 (2014). https:\/\/doi.org\/10.1109\/MAP.2014.6931698","journal-title":"IEEE Antennas Propag. Mag."},{"key":"1824_CR38","doi-asserted-by":"crossref","unstructured":"Paige, C.C., Saunders, M.A.: Lsqr: an algorithm for sparse linear equations and sparse least squares. ACM Trans. Math. Softw. 8(1), 43\u201371 (1982). http:\/\/dblp.uni-trier.de\/db\/journals\/toms\/toms8.html#PaigeS82","DOI":"10.1145\/355984.355989"},{"key":"1824_CR39","doi-asserted-by":"crossref","unstructured":"Pichon, G., Darve, E., Faverge, M., Ramet, P., Roman, J.: Sparse supernodal solver using block low-rank compression. In: 2017 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), pp. 1138\u20131147 (2017)","DOI":"10.1109\/IPDPSW.2017.86"},{"key":"1824_CR40","doi-asserted-by":"publisher","first-page":"A797","DOI":"10.1137\/15M1046939","volume":"39","author":"H Pouransari","year":"2017","unstructured":"Pouransari, H., Coulier, P., Darve, E.: Fast hierarchical solvers for sparse matrices using extended sparsification and low-rank approximation. SIAM J. Sci. Comput. 39, A797\u2013A830 (2017). https:\/\/doi.org\/10.1137\/15M1046939","journal-title":"SIAM J. Sci. Comput."},{"issue":"1\u20132","key":"1824_CR41","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/0377-0427(88)90345-7","volume":"24","author":"Y Saad","year":"1988","unstructured":"Saad, Y.: Preconditioning techniques for nonsymmetric and indefinite linear systems. J. Comput. Appl. Math. 24(1\u20132), 89\u2013105 (1988)","journal-title":"J. Comput. Appl. Math."},{"key":"1824_CR42","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."},{"issue":"6","key":"1824_CR43","doi-asserted-by":"publisher","first-page":"C603","DOI":"10.1137\/16M105890X","volume":"38","author":"J Scott","year":"2016","unstructured":"Scott, J., T\u016fma, M.: Preconditioning of linear least squares by robust incomplete factorization for implicitly held normal equations. SIAM J. Sci. Comput. 38(6), C603\u2013C623 (2016)","journal-title":"SIAM J. Sci. Comput."},{"key":"1824_CR44","unstructured":"Wang, X.: Incomplete factorization preconditioning for linear least squares problems. Ph.D. thesis, University of Illinois at Urbana-Champaign (1994)"},{"key":"1824_CR45","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":"1824_CR46","doi-asserted-by":"crossref","unstructured":"Xia, J.: Efficient structured multifrontal factorization for general large sparse matrices. SIAM J. Sci. Comput. 35 (2013)","DOI":"10.1137\/120867032"},{"key":"1824_CR47","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":"1824_CR48","doi-asserted-by":"publisher","DOI":"10.1002\/nme.6166","author":"K Yang","year":"2016","unstructured":"Yang, K., Pouransari, H., Darve, E.: Sparse hierarchical solvers with guaranteed convergence. Int. J. Numer. Meth. Eng. (2016). https:\/\/doi.org\/10.1002\/nme.6166","journal-title":"Int. J. Numer. Meth. Eng."}],"container-title":["Journal of Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10915-022-01824-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10915-022-01824-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10915-022-01824-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,27]],"date-time":"2022-04-27T13:09:32Z","timestamp":1651064972000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10915-022-01824-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,1]]},"references-count":48,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,5]]}},"alternative-id":["1824"],"URL":"https:\/\/doi.org\/10.1007\/s10915-022-01824-9","relation":{},"ISSN":["0885-7474","1573-7691"],"issn-type":[{"value":"0885-7474","type":"print"},{"value":"1573-7691","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,4,1]]},"assertion":[{"value":"4 March 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 January 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 February 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 April 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 authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"The spaQR code is freely available for download and use in the github repository .","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Code availability"}}],"article-number":"50"}}