Version 2.0.0
2nd August 2021 User documentation
 Recent Changes

Code Download
 Single
 Double
MA49: Sparse overdetermined system: least squares by QR
To compute an orthogonal factorization of a sparse overdetermined matrix \(\mathbf{A}\) and optionally to solve the least squares problem \(\mathrm{ min} \mathbf{b} \mathbf{Ax}_2\). Given a sparse matrix \(\mathbf{A}\) of order \(m \times n\), \(m \ge n\), of full column rank, this subroutine computes the \(\mathbf{QR}\) factorization \(\mathbf{A} = \mathbf{Q} \left [ \begin{array}{c} \mathbf{R} \\ \mathbf{0} \end{array} \right ]\) where \(\mathbf{Q}\) is an \(m \times m\) orthogonal matrix and \(\mathbf{R}\) is an \(n \times n\) upper triangular matrix.
Given an \(n\)vector \(\mathbf{b}\), this subroutine may also compute the minimum 2norm solution of the linear system \(\mathbf{A} ^T \mathbf{x} = \mathbf{b}\), by solving \(\left [ \mathbf{R} ^T \mathbf{0} \right ] \mathbf{z} = \mathbf{b}\) and performing the multiplication \(\mathbf{x} = \mathbf{Q} \mathbf{z}\), or, if the \(\mathbf{Q}\) factor is not stored, by solving \(\mathbf{R} ^T \mathbf{R} \mathbf{z} = \mathbf{b}\) and performing the multiplication \(\mathbf{x} = \mathbf{A} \mathbf{z}\).
The subroutine can also solve systems with the coefficient matrix \(\left [ \begin{array}{c} \mathbf{R} \\ \mathbf{0} \end{array} \right ]\) or \([ {\mathbf{R} ^T \mathbf{0}} ]\), or will compute the product of \(\mathbf{Q}\) or \(\mathbf{Q} ^T\) with a vector.
The method used is based on the multifrontal approach and makes use of Householder transformations. Because an ordering for the columns is chosen using the pattern of the matrix \(\mathbf{A} ^T\)\(\mathbf{A}\), this code is not designed for matrices with full rows.