A Necessary And Sufficient Symbolic Condition For The Existence Of Incomplete Cholesky Factorization

. This paper presents a sufficient condition on sparsity patterns for the existence of the incomplete Cholesky factorization. Given the sparsity pattern P(A) of a matrix A, and a target sparsity pattern P satisfying the condition, incomplete Cholesky factorization successfully completes for all symmetric positive definite matrices with the same pattern P(A). This condition is also necessary in the sense that for a given P(A) and target pattern P , if P does not satisfy the condition then there is at least one symmetric positive definite matrix B whose Cholesky factor has the same sparsity pattern as the Cholesky factor of A, for which incomplete Cholesky factorization fails because of a nonpositive pivot. 1. Introduction. Incomplete Cholesky factorization (IC) is a widely known and effective method of accelerating the convergence of conjugate gradient (CG) iterative methods for solving symmetric positive definite linear systems. A major weakness of IC is that it may break down due to ..