{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T07:38:46Z","timestamp":1771486726182,"version":"3.50.1"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2023,9,19]],"date-time":"2023-09-19T00:00:00Z","timestamp":1695081600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2023,9,30]]},"abstract":"<jats:p>This article presents a fast and approximate multifrontal solver for large sparse linear systems. In a recent work by Liu et\u00a0al., we showed the efficiency of a multifrontal solver leveraging the butterfly algorithm and its hierarchical matrix extension, HODBF (hierarchical off-diagonal butterfly) compression to compress large frontal matrices. The resulting multifrontal solver can attain quasi-linear computation and memory complexity when applied to sparse linear systems arising from spatial discretization of high-frequency wave equations. To further reduce the overall number of operations and especially the factorization memory usage to scale to larger problem sizes, in this article we develop a composite multifrontal solver that employs the HODBF format for large-sized fronts, a reduced-memory version of the nonhierarchical block low-rank format for medium-sized fronts, and a lossy compression format for small-sized fronts. This allows us to solve sparse linear systems of dimension up to 2.7 \u00d7 larger than before and leads to a memory consumption that is reduced by 70% while ensuring the same execution time. The code is made publicly available in GitHub.<\/jats:p>","DOI":"10.1145\/3611662","type":"journal-article","created":{"date-parts":[[2023,8,1]],"date-time":"2023-08-01T11:55:08Z","timestamp":1690890908000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Sparse Approximate Multifrontal Factorization with Composite Compression Methods"],"prefix":"10.1145","volume":"49","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5854-157X","authenticated-orcid":false,"given":"Lisa","family":"Claus","sequence":"first","affiliation":[{"name":"National Energy Research Scientific Computing Center, Lawrence Berkeley National Laboratory, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5981-5234","authenticated-orcid":false,"given":"Pieter","family":"Ghysels","sequence":"additional","affiliation":[{"name":"Applied Mathematics and Computational Research Division, Lawrence Berkeley National Laboratory, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3750-1178","authenticated-orcid":false,"given":"Yang","family":"Liu","sequence":"additional","affiliation":[{"name":"Applied Mathematics and Computational Research Division, Lawrence Berkeley National Laboratory, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9779-2371","authenticated-orcid":false,"given":"Th\u00e1i Anh","family":"Nhan","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, Santa Clara University, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9061-760X","authenticated-orcid":false,"given":"Ramakrishnan","family":"Thirumalaisamy","sequence":"additional","affiliation":[{"name":"Department of Mechanical Engineering, San Diego State University, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0173-9881","authenticated-orcid":false,"given":"Amneet Pal Singh","family":"Bhalla","sequence":"additional","affiliation":[{"name":"Department of Mechanical Engineering, San Diego State University, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0747-698X","authenticated-orcid":false,"given":"Sherry","family":"Li","sequence":"additional","affiliation":[{"name":"Applied Mathematics and Computational Research Division, Lawrence Berkeley National Laboratory, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,9,19]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-013-9714-z"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1137\/120903476"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/3582493"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3242094"},{"key":"e_1_3_2_6_2","volume-title":"SAMRAI Concepts and Software Design","author":"Anderson R.","year":"2013","unstructured":"R. Anderson, W. Arrighi, N. Elliott, B. Gunney, and R. Hornung. 2013. SAMRAI Concepts and Software Design. Technical Report. LLNL."},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/18M1189348"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.2172\/1483828"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719611"},{"key":"e_1_3_2_10_2","unstructured":"Pieter Ghysels. 2014. STRUMPACK: STRUctured Matrix PACKage. Retrieved August 7 2023 from http:\/\/portal.nersc.gov\/project\/sparse\/strumpack\/"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2017.21"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00607-003-0019-1"},{"key":"e_1_3_2_14_2","volume-title":"Simulating the Blood-Muscle-Valve Mechanics of the Heart by an Adaptive and Parallel Version of the Immersed Boundary Method","author":"Griffith Boyce Eugene","year":"2005","unstructured":"Boyce Eugene Griffith. 2005. Simulating the Blood-Muscle-Valve Mechanics of the Heart by an Adaptive and Parallel Version of the Immersed Boundary Method. Ph. D. dissertation. New York University."},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2006.08.019"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/s006070050015"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00607-004-0080-4"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(01)00141-7"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1093\/imanum\/drab020"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479897317661"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/356044.356047"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1137\/16M1074941"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1137\/15M1007173"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2014.2346458"},{"key":"e_1_3_2_25_2","unstructured":"Peter Lindstrom. 2014. zfp: Compressed Floating-Point and Integer Arrays. Retrieved August 7 2023 from https:\/\/computing.llnl.gov\/projects\/zfp"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1137\/1034004"},{"key":"e_1_3_2_27_2","unstructured":"Yang Liu. 2018. ButterflyPACK. Retrieved August 7 2023 from https:\/\/portal.nersc.gov\/project\/sparse\/butterflypack\/"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1137\/20M1349667"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/LAWP.2016.2626786"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1137\/20M1315853"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1137\/120889770"},{"key":"e_1_3_2_32_2","volume-title":"Block Low-Rank Multifrontal Solvers: Complexity, Performance, and Scalability","author":"Mary Th\u00e9o","year":"2017","unstructured":"Th\u00e9o Mary. 2017. Block Low-Rank Multifrontal Solvers: Complexity, Performance, and Scalability. Ph. D. dissertation. l\u2019Universit\u00e9 de Toulouse."},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1002\/mop.4650071707"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2019.03.042"},{"key":"e_1_3_2_35_2","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/978-3-319-25727-3_16","volume-title":"Boundary and Interior Layers, Computational and Asymptotic Methods\u2014BAIL 2014","author":"Nhan T. A.","year":"2015","unstructured":"T. A. Nhan and N. Madden. 2015. Cholesky factorisation of linear systems coming from finite difference approximations of singularly perturbed problems. In Boundary and Interior Layers, Computational and Asymptotic Methods\u2014BAIL 2014, Petr Knobloch (Ed.). Springer International Publishing, Cham, Switzerland, 209\u2013220."},{"key":"e_1_3_2_36_2","unstructured":"Richard Nies and Matthias Hoelzl. 2019. Testing performance with and without block low rank compression in MUMPS and the new PaStiX 6.0 for JOREK nonlinear MHD simulations. arXiv e-prints arXiv:1907.13442 (2019) ."},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1190\/1.2759835"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718072"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1137\/19M1294873"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0031609"},{"key":"e_1_3_2_41_2","first-page":"255","article-title":"Sparse supernodal solver using block low-rank compression: Design, performance and analysis","volume":"27","author":"Pichon Gr\u00e9goire","year":"2018","unstructured":"Gr\u00e9goire Pichon, Eric Darve, Mathieu Faverge, Pierre Ramet, and Jean Roman. 2018. Sparse supernodal solver using block low-rank compression: Design, performance and analysis. Int. J. Comput. Sci. Eng. 27 (2018), 255\u2013270.","journal-title":"Int. J. Comput. Sci. Eng."},{"key":"e_1_3_2_42_2","series-title":"Springer Series in Computational Mathematics","volume-title":"Robust Numerical Methods for Singularly Perturbed Differential Equations (2nd ed.)","author":"Roos H.-G.","year":"2008","unstructured":"H.-G. Roos, M. Stynes, and L. Tobiska. 2008. Robust Numerical Methods for Singularly Perturbed Differential Equations (2nd ed.). Springer Series in Computational Mathematics, Vol. 24. Springer-Verlag, Berlin, Germany."},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1109\/TAP.2021.3137193"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1109\/TAP.2008.926739"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10092-005-0107-z"},{"key":"e_1_3_2_46_2","doi-asserted-by":"crossref","unstructured":"E. Anderson Z. Bai C. Bischof S. Blackford J. Dongarra J. Du Croz A. Greenbaum S. Hammarling A. McKenney and D. Sorensen. 1999. LAPACK Users\u2019 Guide . Vol. 9.","DOI":"10.1137\/1.9780898719604"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3611662","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3611662","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:37:08Z","timestamp":1750178228000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3611662"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,19]]},"references-count":45,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,9,30]]}},"alternative-id":["10.1145\/3611662"],"URL":"https:\/\/doi.org\/10.1145\/3611662","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"value":"0098-3500","type":"print"},{"value":"1557-7295","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,9,19]]},"assertion":[{"value":"2022-11-18","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-07-17","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-09-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}