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 n, of full column rank, this subroutine computes the QR factorization A = Q R 0 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 ATx = b, by solving RT0z = b and performing the multiplication x = Qz, or, if the Q factor is not stored, by solving RTRz = b and performing the multiplication x = Az.

The subroutine can also solve systems with the coefficient matrix R 0 or [RT0], or will compute the product of Q or QT 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 ATA, this code is not designed for matrices with full rows.