NRSAI: An Adaptive and Efficient Preconditioner for Large Sparse Linear Systems

This paper presents a new Residual-based Sparse Approximate Inverse algorithm, designed to be automatic, computationally efficient, and highly parallelizable. After briefly reviewing Frobenius-norm-based preconditioning techniques and identifying two key challenges in this class of methods, we introduce an improved approach that integrates adaptive strategies from the Power Sparse Approximate Inverse algorithm and incomplete LU factorization. The method leverages the Hamilton–Cayley theorem for effective sparsity pattern construction and employs LU decomposition for efficient implementation. Theoretical analysis establishes the convergence properties and computational features of the proposed algorithm. Numerical experiments using real-world data demonstrate that the proposed algorithm significantly outperforms established methods—including the Sparse Approximate Inverse, Power Sparse Approximate Inverse and Residual-based Sparse Approximate Inverse algorithms—with a Generalized Minimal Residual iterative solver, confirming its superior efficiency and practical applicability.