AN IMPROVED INCOMPLETE CHOLESKY FACTORIZATION

Incomplete factorization has been shown to be a good preconditioner fo r the conjugate gradient method on a wide variety of problems. It is w ell known that allowing some fill-in during the incomplete factorizati on can significantly reduce the number of iterations needed for conver gence. Allowing fill-in, however, increases the time for the factoriza tion and for the triangular system solutions. Additionally, it is diff icult to predict a priori how much fill-in to allow and how to allow i t. The unpredictability of the required storage/work and the unknown b enefits of the additional fill-in make such strategies impractical to use in many situations. In this article we motivate, and then present, two ''black-box'' strategies that significantly increase the effectiv eness of incomplete Cholesky factorization as a preconditioner. These strategies require no parameters from the user and do not increase the cost of the triangular system solutions. Efficient implementations fo r these algorithms are described. These algorithms are shown to be suc cessful for a variety of problems from the Harwell-Boeing sparse matri x collection.