Enhancing performance and robustness of ILU preconditioners by blocking and selective transposition

Abstract

Incomplete factorization is one of the most effective general-purpose preconditioning methods for Krylov subspace solvers for large sparse systems of linear equations. Two techniques for enhancing the robustness and performance of incomplete LU factorization for sparse unsymmetric systems are described. A block incomplete factorization algorithm based on the Crout variation of LU factorization is presented. The algorithm is suitable for incorporating threshold-based dropping as well as unrestricted partial pivoting, and it overcomes several limitations of existing incomplete LU factorization algorithms with and without blocking. It is shown that blocking has a threepronged impact: it speeds up the computation of incomplete factors and the solution of the associated triangular systems, it permits denser and more robust factors to be computed economically, and it permits a trade-off with the restart parameter of GMRES to further improve the overall speed and robustness. A highly effective heuristic for improving the quality of preconditioning and subsequent convergence of the associated iterative method is presented. The choice of the Crout variant as the underlying factorization algorithm enables efficient implementation of this heuristic, which has the potential to improve both incomplete and complete sparse LU factorization of matrices that require pivoting for numerical stability.