An improved incomplete Cholesky factorization

ABSTRACT

Incomplete factorization has been shown to be a good preconditioner for the conjugate gradient method on a wide variety of problems. It is well known that allowing some fill-in during the incomplete factorization can significantly reduce the number of iterations needed for convergence. Allowing fill-in, however, increases the time for the factorization and for the triangular system solutions. Additionally, it is difficult to predict a priori how much fill-in to allow and how to allow it. The unpredictability of the required storage/work and the unknown benefits 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 effectiveness 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 for these algorithms are described. These algorithms are shown to be successful for a variety of problems from the Harwell-Boeing sparse matrix collection.

REFERENCES

• 1: AXELSSON, O. AND MUNKSGAARD, N. 1983. Analysis of incomplete factorizations with fixed storage allocation. In Preconditioning Methods Theory and Appltcations, D. Evans, Ed. Gordon and Breach, New York, 219-241.
• 2: I. S. Duff , G. A. Meurant, The effect of ordering on preconditioned conjugate gradients, BIT, v.29 n.4, p.635-657, 1989 [doi>10.1007/BF01932738]
• 3: I. S. Duff , Roger G. Grimes , John G. Lewis, Sparse matrix test problems, ACM Transactions on Mathematical Software (TOMS), v.15 n.1, p.1-14, March 1989 [doi>10.1145/62038.62043]
• 4: FREUND, R. W. AND NACHTIGAL, N. M. 1990. An implementation of the look-ahead Lanczos algorithm for non-Hermitian matrices: Part II. Tech. Rep. RIACS.
• 5: GROPP, W. D., FOULSER, D. E., AND CHANG, S. 1989. CLAM User's Guide. Scientific Computing Associates, New Haven, Conn.
• 6: GUSTAFSSON, I. 1978. A class of first order factorization methods. BIT 18, 2 (June), 142-156.
• 7: HESTENES, M. R. AND STmFEL, E. 1952. Methods of conjugate gradients for solving linear systems. J. Res. Natl. Bur. Stand. 49, 6 (Dec.), 409-436.
• 8: Mark T. Jones , Paul E. Plassmann, Scalable iterative solution of sparse linear systems, Parallel Computing, v.20 n.5, p.753-773, May 1994 [doi>10.1016/0167-8191(94)90004-3]
• 9: KANmL, S. 1966. Estimates for some computational techniques in linear algebra. Math. Comput. 20, 95 (July), 369-378.
• 10: KERSHAW, D.S. 1978. The incomplete Cholesky-conjugate gradient method for the iterative solution of systems of linear equations. J. Comput. Phys. 26, i (Jan.), 43-65.
• 11: MANTEUFFEL, T.A. 1980. An incomplete factorization technique for positive definite linear systems. Math. Comput. 34, 150 (Apr.), 473-497.
• 12: MEIJERINK, J. AND VAN DER VORST, H.A. 1981. Guidelines for the usage of incomplete decompositions in solving sets of linear equations as they occur in practical problems. J. Comput. Phys. 44, 1 (Nov.), 134-155.
• 13: MEIJERINK, J. AND VAN DER VORST, H.A. 1977. An iterative solution method for linear systems of which the coefficient matrix is a symmetric M-matrix. Math. Comput. 31, 137 (Jan.), 148-162.
• 14: N. Munksgaard, Solving Sparse Symmetric Sets of Linear Equations by Preconditioned Conjugate Gradients, ACM Transactions on Mathematical Software (TOMS), v.6 n.2, p.206-219, June 1980 [doi>10.1145/355887.355893]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Sparse, structured, and very large systems (direct and iterative methods)

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Linear systems (direct and iterative methods)

General Terms:
Algorithms

Keywords:
incomplete Cholesky, incomplete factorization, preconditioners, sparse matrices