Robust preconditioning for large sparse least squares problems

Michele Benzi

Department of Mathematics, Emory University, Atlanta GA 30322


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 LDL' 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. The method is also applicable to more general problems arising in constrained optimization. Numerical experiments illustrating the performance of the preconditioner will be presented. We will compare our approach with existing techniques based on incomplete QR (or LQ) factorizations. This is joint work with Miroslav Tuma (Academy of Sciences of the Czech Republic, Prague, CZ).