Properties of a class of preconditioners for weighted least squares problems

Venansius Baryamureeba, Trond Steihaug and Yin Zhang

A sequence of weighted linear least squares problems arises from interior-point methods for linear programming where the changes from one problem to the next are the weights and the right hand side. One approach for solving such a weighted linear least squares problem is to apply a preconditioned conjugate gradient method to the normal equations where the preconditioner is based on a low-rank correction to the Cholesky factorization of a previous coefficient matrix. In this paper, we establish theoretical results for such preconditioners that provide guidelines for the construction of preconditioners of this kind. We also present preliminary numerical experiments to validate our theoretical results and to demonstrate the effectiveness of this approach.

Technical Report No. 170, Department of Informatics, University of Bergen, N-5020 Bergen, Norway and Technical Report No. TR99-16, Department of Computational and Applied Mathematics, Rice University, Houston, Texas 77005, USA. April 30, 1999 (Revised July 6, 1999)