Incomplete Cholesky Factorization with Sparsity Pattern Modification

This paper proposes, analyzes, and numerically tests methods to assure the existence of incomplete Cholesky (IC) factorization preconditioners, based solely on the target sparsity pattern for the triangular factor R. If the sparsity pattern has a simple property (called property C+), then the IC factor exists in exact arithmetic. Two algorithms for modifying the target sparsity pattern to have property C+ are proposed, one based on adding elements into the set of retained elements and the other based on dropping elements. Tests show that the modifications do ensure the numerical existence of the IC factor, and the resulting preconditioners are effective in accelerating the conjugate gradient iteration method. 1 Introduction The incomplete Cholesky (IC) factorization is one of the most important and commonly used preconditioners for iterative methods of solving large sparse symmetric positive definite linear systems [4]. Its major weakness is a lack of robustness, by which we mean the ..