## Version 1.2.0

Code Download

• Single
• Double

### 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||b-Ax|{|}_{2}$. Given a sparse matrix $A$ of order $m×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×m$ orthogonal matrix and $R$ is an $n×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.