# Systems Optimization Laboratory

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

• REFERENCES:
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.)
• RELEASE:
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.