A Multilevel Block Incomplete Cholesky Preconditioner for Solving
Rectangular Sparse Matrices from Linear Least Squares Problems

Jun Zhang and Tong Xiao
Laboratory for High Performance Scientific Computing and Computer Simulation
Department of Computer Science
University of Kentucky
773 Anderson Hall
Lexington, KY 40506-0046, USA


An incomplete factorization method for preconditioning symmetric positive definite matrices is introduced to solve normal equations. The normal equations are formed as a means to solve rectangular matrices from linear least squares problems. The procedure is based on a block incomplete Cholesky factorization and a multilevel recursive strategy with an approximate Schur complement matrix formed implicitly. A diagonal perturbation strategy is implemented to enhance factorization robustness. The factors obtained are used as a preconditioner for the conjugate gradient method. Numerical experiments are used to show the robustness and efficiency of this preconditioning technique, and to compare it with two other preconditioners.

Key words: incomplete Cholesky factorization, multilevel IC preconditioner, normal equation, conjugate gradient.

Download the compressed postscript file bicm.ps.gz, or the PDF file bicm.pdf.gz.
This paper has been accepted for publication in Journal of Applied Mathematics and Computing.

Technical Report No. 317-01, Department of Computer Science, University of Kentucky, Lexington, KY, 2001. This research was supported in part by the U.S. National Science Foundation under grants CCR-9902022, CCR-9988165 and CCR-0043861.