### MA49 Sparse over-determined system: least squares by QR

To compute an orthogonal factorization of a sparse overdetermined matrix
$A$
and optionally to solve the least squares problem
$min\left|\right|b-Ax|{|}_{2}$. Given a
sparse matrix $A$
of order $m\times n$,
$m\ge n$,
of full column rank, this subroutine computes the
$QR$ factorization
$A=Q\left[\begin{array}{c}\hfill R\hfill \\ \hfill 0\hfill \end{array}\right]$where
$Q$ is an
$m\times m$ orthogonal
matrix and $R$
is an $n\times n$
upper triangular matrix.

Given an $n$-vector
$b$, this
subroutine may also compute the minimum 2-norm solution of the linear system
${A}^{T}x=b$, by solving
$\left[{R}^{T}0\right]z=b$ and performing the
multiplication $x=Qz$, or, if the
$Q$ factor is not stored, by
solving ${R}^{T}Rz=b$ and performing
the multiplication $x=Az$.

The subroutine can also solve systems with the coeﬃcient matrix
$\left[\begin{array}{c}\hfill R\hfill \\ \hfill 0\hfill \end{array}\right]$or
$\left[{R}^{T}0\right]$, or will compute
the product of $Q$
or ${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
${A}^{T}$$A$,
this code is not designed for matrices with full rows.