SOL Logo

Systems Optimization Laboratory

Stanford University
Dept of Management Science and Engineering (MS&E)

Huang Engineering Center

Stanford, CA 94305-4121  USA

CRAIG: Sparse Equations

  • AUTHORS: Chris Paige, Michael Saunders.
  • CONTRIBUTORS: Dominique Orban.
  • CONTENTS: Implementation of a conjugate-gradient type method for solving sparse linear equations \begin{align*} \text{Solve } & Ax=b \\ \text{minimize } \|x\| \text{ s.t. } & Ax=b, \end{align*} where the matrix \(A\) may be square or rectangular and may have any rank, as long as \(Ax=b\) is compatible. \(A\) is represented by a routine for computing \(Av\) and \(A^T u\) for given vectors \(v\) and \(u\).

    The method is based on the Golub-Kahan bidiagonalization process. It is algebraically equivalent to applying CG to the symmetric system \( A A^T y = b \) and setting \(x = A^T y\), but it has better numerical properties, especially if \(A\) is ill-conditioned.

    For CRAIG's approximate solutions \(x_k\), the norms \(\|x_k\|\) increase monotonically and the errors \(\|x - x_k\|\) decrease monotonically.

    If \(A\) is symmetric, use SYMMLQ, MINRES, or MINRES-QLP.

    If \(Ax = b\) has no solution (is incompatible), use LSQR or LSMR.

    C. C. Paige and M. A. Saunders, LSQR: An algorithm for sparse linear equations and sparse least squares, TOMS 8(1), 43-71 (1982). (See p58.)
    15 Aug 2014: This webpage created. craigSOL.m implemented to complement lsqrSOL.m.
    19 Aug 2014: Beware: the estimate of cond(A) seems too high and may cause early termination. If so, it is easy to disable the stopping tests involving Acond.
    28 Aug 2014: Fixed glitches found by Dominique Orban.