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.

By: Anshul Gupta

Published in: RC25577 in 2015


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to reports@us.ibm.com .