A robust preconditioner with low memory requirements for large sparse least squares problems

Michele Benzi

Department of Mathematics and Computer Science
Emory University
Atlanta, Georgia 30322, USA

Mirosla V. Tuma

Institute of Computer Science
Academy of Sciences of the Czech Republic
Pod vodarenskou vez 2
182 07 Prague 8, Czech Republic


Abstract

We describe a technique for constructing robust preconditioners for the CGNR method applied to the solution of large and sparse least squares problems. Our algorithm computes an incomplete LDLT factorization of the normal equations matrix without the need to form the normal matrix itself. The preconditioner is reliable (pivot breakdowns cannot occur) and has low intermediate storage requirements. Numerical experiments illustrating the performance of the preconditioner are presented.

Key words: Large sparse least squares problems, preconditioned CGNR, robust incomplete factorization, incomplete C-orthogonalization

AMS subject classifications: Primary 65F10, 65F20, 65F25, 65F35, 65F50. Secondary 15A06.