• STFC home
  The Science and Technology Facilities Council
• HSL home
  About the HSL Mathematical Software Library
• HSL 2013
  Our current release
• HSL archive
  Older packages available at no cost
• Academic access
  Free access for teaching and research
• The Numerical Analysis Group
  About the research group behind HSL
• Contact us
  Our contact details

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 coefficient 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.