{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T06:48:18Z","timestamp":1762325298089,"version":"3.41.0"},"reference-count":77,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2022,9,10]],"date-time":"2022-09-10T00:00:00Z","timestamp":1662768000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Empire State Development grant NYS","award":["28451"],"award-info":[{"award-number":["28451"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2022,9,30]]},"abstract":"<jats:p>\n            We introduce a software package called\n            <jats:italic>Hybrid Incomplete Factorization with Iterative Refinement (HIFIR)<\/jats:italic>\n            for preconditioning sparse, unsymmetric, ill-conditioned, and potentially singular systems. HIFIR computes a\n            <jats:italic>hybrid incomplete factorization<\/jats:italic>\n            <jats:italic>(HIF)<\/jats:italic>\n            , which combines multilevel incomplete LU factorization with a truncated, rank-revealing QR (RRQR) factorization on the final Schur complement. This novel hybridization is based on the new theory of\n            <jats:italic>\u03f5-accurate approximate generalized inverse (AGI)<\/jats:italic>\n            . It enables near-optimal preconditioners for consistent systems and enables flexible GMRES to solve inconsistent systems when coupled with iterative refinement. In this article, we focus on some practical algorithmic and software issues of HIFIR. In particular, we introduce a new inverse-based rook pivoting (IBRP) into ILU, which improves the robustness and the overall efficiency for some ill-conditioned systems by significantly reducing the size of the final Schur complement for some systems. We also describe the software design of HIFIR in terms of its efficient data structures for supporting rook pivoting in a multilevel setting, its template-based generic programming interfaces for mixed-precision real and complex values in C++, and its user-friendly high-level interfaces in MATLAB and Python. We demonstrate the effectiveness of HIFIR for ill-conditioned or singular systems arising from several applications, including the Helmholtz equation, linear elasticity, stationary incompressible Navier\u2013Stokes (INS) equations, and time-dependent advection-diffusion equation.\n          <\/jats:p>","DOI":"10.1145\/3536165","type":"journal-article","created":{"date-parts":[[2022,5,10]],"date-time":"2022-05-10T11:15:56Z","timestamp":1652181356000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["HIFIR: Hybrid Incomplete Factorization with Iterative Refinement for Preconditioning Ill-Conditioned and Singular Systems"],"prefix":"10.1145","volume":"48","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7312-7510","authenticated-orcid":false,"given":"Qiao","family":"Chen","sequence":"first","affiliation":[{"name":"Stony Brook University, Stony Brook, New York, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7111-9813","authenticated-orcid":false,"given":"Xiangmin","family":"Jiao","sequence":"additional","affiliation":[{"name":"Stony Brook University, Stony Brook, New York, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,9,10]]},"reference":[{"issue":"100","key":"e_1_3_3_2_2","article-title":"The FEniCS project version 1.5","volume":"3","author":"Aln\u00e6s Martin","year":"2015","unstructured":"Martin Aln\u00e6s, Jan Blechta, Johan Hake, August Johansson, Benjamin Kehlet, Anders Logg, Chris Richardson, Johannes Ring, Marie E. Rognes, and Garth N. Wells. 2015. The FEniCS project version 1.5. Archive of Numerical Software 3, 100 (2015), 9\u201323.","journal-title":"Archive of Numerical Software"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/1024074.1024081"},{"key":"e_1_3_3_4_2","first-page":"121","volume-title":"Proceedings of the International Workshop on Applied Parallel Computing","author":"Amestoy Patrick R.","year":"2000","unstructured":"Patrick R. Amestoy, Iain S. Duff, Jean-Yves L\u2019Excellent, and Jacko Koster. 2000. MUMPS: A general purpose distributed memory sparse solver. In Proceedings of the International Workshop on Applied Parallel Computing. Springer, 121\u2013130."},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/04060593X"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.2172\/1614847"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02070824"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/MCSE.2010.118"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcph.2002.7176"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/050646421"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827597326845"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1002\/nla.320"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1137\/S106482750240649X"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1137\/0611021"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611971484"},{"key":"e_1_3_3_16_2","first-page":"917","volume-title":"Proceedings of the Encyclopedia of Parallel Computing","author":"Bollh\u00f6fer Matthias","year":"2011","unstructured":"Matthias Bollh\u00f6fer, Jos\u00e9 I. Aliaga, Alberto F. Mart\u00edn, and Enrique S. Quintana-Ort\u00ed. 2011. ILUPACK. In Proceedings of the Encyclopedia of Parallel Computing. Springer, 917\u2013926."},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1137\/040608374"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1002\/9780470753767"},{"key":"e_1_3_3_19_2","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/0024-3795(87)90103-0","article-title":"Rank revealing QR factorizations","volume":"88","author":"Chan Tony F.","year":"1987","unstructured":"Tony F. Chan. 1987. Rank revealing QR factorizations. Linear Algebra and Its Applications 88 (1987), 67\u201382.","journal-title":"Linear Algebra and Its Applications"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01933580"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1002\/nla.2400"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1002\/fld.5039"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-0427(97)00171-4"},{"issue":"1","key":"e_1_3_3_24_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2049662.2049663","article-title":"The University of Florida sparse matrix collection","volume":"38","author":"Davis Timothy A.","year":"2011","unstructured":"Timothy A. Davis and Yifan Hu. 2011. The University of Florida sparse matrix collection. ACM Transactions on Mathematical Software 38, 1 (2011), 1\u201325.","journal-title":"ACM Transactions on Mathematical Software"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1137\/0719025"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1017\/S096249290000235X"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479899358443"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1137\/0902019"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1137\/040608817"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22061-6_10"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1137\/10079687X"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.5555\/906279"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1002\/nme.2579"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1002\/nla.2215"},{"key":"e_1_3_3_35_2","doi-asserted-by":"crossref","DOI":"10.56021\/9781421407944","volume-title":"Matrix Computations (4th ed.)","author":"Golub Gene H.","year":"2013","unstructured":"Gene H. Golub and Charles F. Van Loan. 2013. Matrix Computations (4th ed.). Johns Hopkins."},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3014057"},{"key":"e_1_3_3_37_2","unstructured":"Ga\u00ebl Guennebaud Beno\u00eet Jacob et\u00a0al. 2010. Eigen v3. (2010). Retrieved from http:\/\/eigen.tuxfamily.org."},{"key":"e_1_3_3_38_2","volume-title":"WSMP: Watson Sparse Matrix Package (Part-III: Iterative Solution of Sparse Systems) Version 20.12","author":"Gupta Anshul","year":"2021","unstructured":"Anshul Gupta. 2021. WSMP: Watson Sparse Matrix Package (Part-III: Iterative Solution of Sparse Systems) Version 20.12. Technical Report. IBM T. J. Watson Research Center. Retrieved from http:\/\/www.research.ibm.com\/projects\/wsmp."},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.5555\/1958573.1958596"},{"key":"e_1_3_3_40_2","volume-title":"WSMP: A High-performance Shared- and Distributed-memory Parallel Sparse Linear Equation Solver","author":"Gupta Anshul","year":"2001","unstructured":"Anshul Gupta, Mahesh Joshi, and Vipin Kumar. 2001. WSMP: A High-performance Shared- and Distributed-memory Parallel Sparse Linear Equation Solver. Technical Report. IBM T. J. Watson Research Center."},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1137\/070696313"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.2172\/15002765"},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/1089014.1089021"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.6028\/jres.049.044"},{"issue":"7","key":"e_1_3_3_45_2","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1145\/366622.366647","article-title":"Algorithm 65: Find","volume":"4","author":"Hoare Charles A. R.","year":"1961","unstructured":"Charles A. R. Hoare. 1961. Algorithm 65: Find. Communications of the ACM 4, 7 (1961), 321\u2013322.","journal-title":"Communications of the ACM"},{"key":"e_1_3_3_46_2","volume-title":"hypre Documentation Release 2.21.0","author":"Developers hypre","year":"2021","unstructured":"hypre Developers. 2021. hypre Documentation Release 2.21.0. Lawrence Livermore National Laboratory."},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.1137\/110830125"},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.1137\/0905067"},{"key":"e_1_3_3_49_2","doi-asserted-by":"publisher","DOI":"10.1137\/20M1364126"},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.1137\/20M1387985"},{"key":"e_1_3_3_51_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2007.02.021"},{"key":"e_1_3_3_52_2","doi-asserted-by":"publisher","DOI":"10.1137\/S106482759935808X"},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.1002\/nla.2212"},{"key":"e_1_3_3_54_2","unstructured":"STFC Rutherford Appleton Laboratory. 2021. HSL_MC64. Permute and scale a sparse unsymmetric or rectangular matrix to put large entries on the diagonal. (2021). Retrieved from https:\/\/www.hsl.rl.ac.uk\/catalogue\/hsl_mc64.html. Accessed: 2021-3-16"},{"key":"e_1_3_3_55_2","first-page":"75","article-title":"Crout versions of ILU factorization with pivoting for sparse symmetric matrices","volume":"20","author":"Li Na","year":"2005","unstructured":"Na Li and Yousef Saad. 2005. Crout versions of ILU factorization with pivoting for sparse symmetric matrices. Electronic Transactions on Numerical Analysis 20 (2005), 75\u201385.","journal-title":"Electronic Transactions on Numerical Analysis"},{"key":"e_1_3_3_56_2","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827502405094"},{"key":"e_1_3_3_57_2","doi-asserted-by":"publisher","DOI":"10.1145\/1089014.1089017"},{"key":"e_1_3_3_58_2","doi-asserted-by":"publisher","DOI":"10.1145\/1916461.1916467"},{"key":"e_1_3_3_59_2","doi-asserted-by":"publisher","DOI":"10.1145\/1731022.1731030"},{"key":"e_1_3_3_60_2","doi-asserted-by":"publisher","DOI":"10.1137\/030602022"},{"key":"e_1_3_3_61_2","doi-asserted-by":"publisher","DOI":"10.1002\/pamm.200700911"},{"key":"e_1_3_3_62_2","doi-asserted-by":"publisher","DOI":"10.1137\/130946009"},{"key":"e_1_3_3_63_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cma.2019.03.052"},{"key":"e_1_3_3_64_2","doi-asserted-by":"publisher","DOI":"10.1137\/0712047"},{"key":"e_1_3_3_65_2","doi-asserted-by":"publisher","DOI":"10.1145\/355984.355989"},{"key":"e_1_3_3_66_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2017.01.050"},{"key":"e_1_3_3_67_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-0427(00)00406-4"},{"key":"e_1_3_3_68_2","doi-asserted-by":"publisher","DOI":"10.1525\/9780520325883-032"},{"key":"e_1_3_3_69_2","doi-asserted-by":"publisher","DOI":"10.1016\/0377-0427(88)90345-7"},{"key":"e_1_3_3_70_2","doi-asserted-by":"publisher","DOI":"10.1137\/0914028"},{"key":"e_1_3_3_71_2","doi-asserted-by":"publisher","DOI":"10.5555\/829576"},{"key":"e_1_3_3_72_2","doi-asserted-by":"publisher","DOI":"10.1137\/0907058"},{"key":"e_1_3_3_73_2","doi-asserted-by":"publisher","DOI":"10.1002\/nla.279"},{"key":"e_1_3_3_74_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-322-89849-4_39"},{"key":"e_1_3_3_75_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-0427(00)00515-X"},{"key":"e_1_3_3_76_2","volume-title":"Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations","author":"Smith Barry F.","year":"1996","unstructured":"Barry F. Smith, Petter E. Bj\u00f8rstad, and William D. Gropp. 1996. Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations. Cambridge University Press."},{"key":"e_1_3_3_77_2","doi-asserted-by":"publisher","DOI":"10.1016\/0045-7930(73)90027-3"},{"key":"e_1_3_3_78_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41592-019-0686-2"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3536165","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3536165","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:54Z","timestamp":1750188654000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3536165"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,10]]},"references-count":77,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,9,30]]}},"alternative-id":["10.1145\/3536165"],"URL":"https:\/\/doi.org\/10.1145\/3536165","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"type":"print","value":"0098-3500"},{"type":"electronic","value":"1557-7295"}],"subject":[],"published":{"date-parts":[[2022,9,10]]},"assertion":[{"value":"2021-06-17","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-05-02","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-09-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}