HIFIR is a multilevel precondition for preconditioning sparse, unsymmetric, ill-conditioned, and potentially singular systems. HIFIR computes a hybrid incomplete factorization, which combines multilevel incomplete LU factorization with a truncated, rank-revealing QR factorization on the final Schur complement. This novel hybridization is based on the new theory of approximate generalized inverse and ϵ-accuracy. It enables near-optimal preconditioners for consistent systems and enables flexible GMRES to solve inconsistent systems when coupled with iterative refinement. In this paper, we focus on some practical algorithmic and software issues of HIFIR. In particular, we introduce a new inverse-based rook pivoting into ILU, which improves the robustness and the overall efficiency in solving ill-conditioned systems by significantly reducing the size of the final Schur complement for some systems. HIFIR has efficient data structures for supporting rook pivoting in a multilevel setting, and it provides template-based header-only programming interfaces for mixed-precision real and complex values in C++ and user-friendly high-level interfaces in MATLAB and Python. HIFIR has been demonstrated to be effective for ill-conditioned or singular systems arising from several applications, including the Helmholtz equation, linear elasticity, stationary incompressible Navier--Stokes equations, and time-dependent advection-diffusion equation.

 

Xiangmin Jiao (Lead PI)

Qiao Chan

 

Publications:

• Chen, Qiao, and Xiangmin Jiao. "HIFIR: Hybrid Incomplete Factorization with Iterative Refinement for Preconditioning Ill-conditioned and Singular Systems." ACM Transactions on Mathematical Software, 2022. DOI: https://doi.org/10.1145/3536165
• Chen, Qiao, Aditi Ghai, and Xiangmin Jiao. "HILUCSI: Simple, robust, and fast multilevel ILU for large‐scale saddle‐point problems from PDEs." Numerical Linear Algebra with Applications 28.6 (2021): e2400. DOI:  https://doi.org/10.1002/nla.2400

• https://github.com/hifirworks/hifir
• https://github.com/hifirworks/hifir4py
• https://github.com/hifirworks/hifir4m