Iain Duff
Preconditioning of Least-Squares Problems by Identifying Basic Variables

STFC - Rutherford Appleton Laboratory
Harwell-Oxford
OX11 0QX
UK
iain.duff@stfc.ac.uk
Mario Arioli

We study the preconditioning of the augmented system formulation of the least squares problem $\min_x \vert\vert b - A x \vert\vert^2_2$ , viz.

$$\left[ \begin{array}{cc} I_m & A\ A^T & 0 \end{array}\right] \; \left[ \begin{array}{c} r\ x \end{array}\right],$$

where A is a sparse matrix of order $m \times n$ with full column rank and $r$ is the residual vector equal to $b - Ax$ . We split the matrix $A$ into basic and non-basic parts so that $P A = \left[ \begin{array}{c} B\ N \end{array}\right],$ where $P$ is a permutation matrix, and we use the preconditioner

$$M = \left[ \begin{array}{cc} I & 0\ 0 & B^{-T} \end{array}\right]$$

to symmetrically precondition the system to obtain, after a simple block Gaussian elimination, the reduced symmetric quasi-definite (SQD) system

$$\left[ \begin{array}{cc} I_{m-n} & N B^{-1}\\ B^{-T}N^T & -I_n \e... ... \end{array} \right] = \left[ \begin{array}{c} b_N\\ -b_B \end{array} \right] .$$

We discuss the conditioning of the SQD system with some minor extensions to standard eigenanalysis, show the difficulties associated with choosing the basis matrix $B$ , and discuss how sparse direct techniques can be used to choose it. We also comment on the common case where A is an incidence matrix and the basis can be chosen graphically.