{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,23]],"date-time":"2026-10-23T20:34:48Z","timestamp":1792787688850,"version":"4.5.0"},"reference-count":41,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-11-LABX-0040-CIMI"],"award-info":[{"award-number":["ANR-11-LABX-0040-CIMI"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-11-IDEX-0002-02"],"award-info":[{"award-number":["ANR-11-IDEX-0002-02"]}],"id":[{"id":"10.13039\/501100001665","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>Matrices coming from elliptic partial differential equations have been shown to have a low-rank property: well-defined off-diagonal blocks of their Schur complements can be approximated by low-rank products, and this property can be efficiently exploited in multifrontal solvers to provide a substantial reduction of their complexity. Among the possible low-rank formats, the block low-rank (BLR) format is easy to use in a general purpose multifrontal solver and has been shown to provide significant gains compared to full-rank on practical applications. However, unlike hierarchical formats, such as $\\mathcal{H}$ and HSS, its theoretical complexity was unknown. In this paper, we extend the theoretical work done on hierarchical matrices in order to compute the theoretical complexity of the BLR multifrontal factorization. We then present several variants of the BLR multifrontal factorization, depending on the strategies used to perform the updates in the frontal matrices and on the constraints on how numerical pivoting is handled. We show how these variants can further reduce the complexity of the factorization. In the best case (3D, constant ranks), we obtain a complexity of the order of $O(n^{4\/3})$. We provide an experimental study with numerical results to support our complexity bounds.<\/jats:p>","DOI":"10.1137\/16m1077192","type":"journal-article","created":{"date-parts":[[2017,8,30]],"date-time":"2017-08-30T18:59:56Z","timestamp":1504119596000},"page":"A1710-A1740","source":"Crossref","is-referenced-by-count":64,"title":["On the Complexity of the Block Low-Rank Multifrontal Factorization"],"prefix":"10.1137","volume":"39","author":[{"given":"Patrick","family":"Amestoy","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alfredo","family":"Buttari","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jean-Yves","family":"L'Excellent","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Theo","family":"Mary","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2017,8,30]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1137\/120903476"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1190\/geo2016-0052.1"},{"key":"atypb3","first-page":"1209","volume-title":"Encyclopedia of Parallel Computing","author":"Amestoy P. R.","year":"2011"},{"key":"atypb4","first-page":"1232","volume-title":"Encyclopedia of Parallel Computing","author":"Amestoy P. R.","year":"2011"},{"key":"atypb5","volume-title":"Proceedings of SIAM Conference on Parallel Processing (SIAM PP16)","author":"Amestoy P. R.","year":"2016"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2015.10.012"},{"key":"atypb7","volume-title":"CoRR, https:\/\/arxiv.org\/abs\/1410.2697","author":"Aminfar A.","year":"2014"},{"key":"atypb8","volume-title":"LAPACK Users' Guide","author":"Anderson E.","year":"1995","edition":"3"},{"key":"atypb9","volume-title":"Proceedings of SIAM Conference on Parallel Processing (SIAM PP16)","author":"Anton J.","year":"2016"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-04-01716-8"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1137\/060669747"},{"key":"atypb12","series-title":"Lecture Notes in Computational Science and Engineering (LNCSE)","volume-title":"Hierarchical Matrices: A Means to Efficiently Solve Elliptic Boundary Value Problems","volume":"63","author":"Bebendorf M.","year":"2008"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1007\/s00211-002-0445-6"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/S0955-7997(02)00152-2"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479803436652"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1137\/030602678"},{"key":"atypb17","volume-title":"Direct Methods for Sparse Matrices","author":"Duff I. S.","year":"1986"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1137\/050629598"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1145\/356044.356047"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.20358"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1137\/0710032"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1137\/15M1010117"},{"key":"atypb23","unstructured":"A. Gillman,\n                      Fast Direct Solvers for Elliptic Partial Differential Equations\n                      , Ph.D. thesis, University of Colorado, 2011."},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1007\/s11464-012-0188-3"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1007\/s00607-003-0019-1"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1007\/s006070050015"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1007\/s00607-004-0080-4"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.21582"},{"key":"atypb29","volume-title":"Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices, Version 4.0","author":"Karypis G.","year":"1998"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1137\/110825753"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1137\/0611010"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1137\/1034004"},{"key":"atypb33","first-page":"2415","volume-title":"Springer","author":"Peir\u00f3 J.","year":"2005"},{"key":"atypb34","volume-title":"ArXiv e-prints","author":"Pouransari H.","year":"2015"},{"key":"atypb35","unstructured":"D. Ruiz,\n                      A scaling algorithm to equilibrate both rows and columns norms in matrices\n                      , Tech. Rep. RT\/APO\/01\/4, ENSEEIHT-IRIT, 2001."},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1145\/356004.356006"},{"key":"atypb37","volume-title":"``Compress and eliminate","author":"Sushnikova D. A.","year":"2016"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1145\/2830569"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1137\/120867032"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1137\/09074543X"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1002\/nla.691"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M1077192","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:58:27Z","timestamp":1787335107000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1077192"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1]]},"references-count":41,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["10.1137\/16M1077192"],"URL":"https:\/\/doi.org\/10.1137\/16m1077192","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,1]]}}}