Incomplete Cholesky Factorization with Sparsity

Pattern Modification

<_author_search_(xiaoge wang)>Xiaoge Wang

Department of Computer Science

Indiana University - Bloomington

<_author_search_(kyle gallivan)>Kyle Gallivan

Department of Electrical and Computer Engineering

University of Illinois- Urbana

<_author_search_(randall bramley)>Randall Bramley

Department of Computer Science

Indiana University - Bloomington ?

December 21, 1993

Abstract

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 failure of

?Work supported by NSF grants CDA-9309746 and CCR-9120105