What is it about?

We introduce a software package called HIFIR 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. It enables near-optimal preconditioners for consistent systems and enables flexible GMRES to solve inconsistent systems when coupled with iterative refinement.

Featured Image

Why is it important?

Krylov subspace (KSP) methods, such as GMRES and BiCGSTAB, are widely used for solving large-scale sparse unsymmetric or indefinite linear systems, especially those arising from numerical discretizations of partial differential equations (PDEs). For relatively ill-conditioned matrices, the KSP methods can significantly benefit from a robust and efficient precondition. 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–Stokes equations, and time-dependent advection-diffusion equation.


Unlike previous software packages, HIFIR is designed to solve singular and near-singular (aka ill-conditioned) systems, including finding least-squares solutions for consistent singular systems, null-space vectors of singular matrices, and pseudoinverse solutions for inconsistent systems. This unique feature is backed by a new theory of epsilon-accurate AGI, and a new algorithm that combines multilevel incomplete LU factorization with an RRQR on the final Schur complement. We also introduce a new inverse-based rook pivoting into ILU, which improves the robustness and the overall efficiency of some ill-conditioned systems by significantly reducing the size of the final Schur complement for some systems

Xiangmin Jiao
Stony Brook University

Read the Original

This page is a summary of: HIFIR: Hybrid Incomplete Factorization with Iterative Refinement for Preconditioning Ill-Conditioned and Singular Systems, ACM Transactions on Mathematical Software, September 2022, ACM (Association for Computing Machinery), DOI: 10.1145/3536165.
You can read the full text:



The following have contributed to this page