Enhancing Performance and Robustness of ILU Preconditioners through Blocking and Selective Transposition

Abstract. Incomplete factorization is one of the most effective general-purpose preconditioning methods for Krylov subspace methods for solving 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 for incomplete factorization based on the Crout variation of dense LU factorization is presented. The algorithm is suitable for incorporating threshold-based dropping as well as partial pivoting. It is shown that blocking has a three-pronged 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 GMRES 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.