Solution of Large-Scale Weighted Least Squares Problems
by
Venansius Baryamureeba
Department of Informatics, University of Bergen, 5020 Bergen, Norway

Solution of Large-Scale
Weighted Least Squares Problems

Venansius Baryamureeba

A sequence of least squares problems min_yk||G_k^1/2A^Ty_k-h_k||₂, k >= 0, where G_k is an n×n positive definite diagonal weight matrix, and A an m×n (m <= n) sparse matrix with some dense columns; has many applications in linear programming, electrical networks, elliptic boundary value problems, and structural analysis. We suggest a mixture of a direct method and an iterative method to solve the normal equations. Further, we discuss a class of preconditioners based on low-rank corrections.

Consider a sequence of weighted least squares problems

min yk  ||ATyk-hk||Gk, k = 0, 1, ... .

(1)

Define ||(.)||_Gk = ||G_k^1/2(.)||₂. Then the solution of (1) is given by the normal equations

AGkATyk = AGkhk, k = 0, 1, ... , .

(2)

Let A=[A₁  A₂] be a partition of A, where A₁ in Re^m×p, A₂ in Re^m×(n-p), m <= p <= n, and A₁ have full rank m. Let the n×n positive definite diagonal matrices G and K be partitioned such that

AGAT = A1G1A1T + A2G2A2T  and  AKAT = A1K1A1T + A2K2A2T.

In applications where the problem matrix A contains some dense columns, an effective preconditioner is of the form A₁K₁A₁^T. In this paper we establish bounds on the spectral condition number of the preconditioned matrix (A₁K₁A₁^T)^-1AGA^T and suggest how to form K₁.

A closely related recent work to this present paper is by Baryamureeba, Steihaug, and Zhang [1], Wang and O'Leary [2]; where the authors propose preconditioning strategies for the normal equation system based on low-rank corrections similar to what is discussed in this paper. However, both papers do not discuss how to handle the case when A contains some dense columns.

References

[]

[1] V. Baryamureeba, T. Steihaug, and Y. Zhang, Properties of a class of preconditioners for weighted least squares problems, Technical Report No. 170, Department of Informatics, University of Bergen, 5020 Bergen, Norway, April 30, 1999 (Revised July 6, 1999). Submitted to Mathematical Programming.

[]

[2] W. Wang and D.P. O'Leary, Adaptive use of iterative methods in interior point methods for linear programming, Computer Science Department Report CS-TR-3560, Institute for Advanced Computer Studies Report UMIACS-95-111, University of Maryland, November 1995.

Date received: February 1, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caeb-79.