  # Systems Optimization Laboratory

## CGLS: CG method for Ax = b and Least Squares

• AUTHOR: Michael Saunders
CONTRIBUTORS: Per Christian Hansen, Folkert Bleichrodt, Christopher Fougner

• CONTENTS:
A MATLAB implementation of CGLS, the Conjugate Gradient method for unsymmetric linear equations and least squares problems: \begin{align*} \text{Solve } & Ax=b \\ \text{or minimize } & \|Ax-b\|^2 \\ \text{or solve } & (A^T A + sI)x = A^T b, \end{align*} where the matrix $$A$$ may be square or rectangular (represented by an M-file for computing $$Ax$$ and $$A^Tx$$) and $$s$$ is a scalar (positive or negative).
The method is stable if $$s = 0$$ or $$s > 0$$. More generally, it should be stable if $$A^T A + sI$$ is positive definite. Otherwise it may be unstable.

• REFERENCES:
Documented in the MATLAB file below.
Special feature: This is a simple CG-type code for unsymmetric equations and least squares, with the option of a negative shift. However, use with caution if $$s < 0$$.

If $$s \ge 0$$, we recommend LSQR or LSMR. Do not use a symmetric CG code on the normal equations, even though it is equivalent to LSQR in exact arithmetic.

With $$s = 0$$, the method is due to Hestenes and Stiefel (1952). See the first LSQR paper, Paige and Saunders (1982a), ACM TOMS 8(1), 43-71. Trivial changes are needed to allow an arbitrary shift.

• RELEASE:
01 Sep 1999: First version, implemented at DTU, Denmark.
15 Apr 2013: More polished version contributed by Folkert Bleichrodt, Centrum Wiskunde & Informatica (CWI), Amsterdam, The Netherlands.
02 Sep 2014: CUDA implementation contributed by Christopher Fougner, ICME, Stanford.
08 Feb 2015: CUDA version can treat $$A$$ as a matrix or an operator.
09 Feb 2015: CUDA version allows $$A,b,x$$ to be complex (but $$s$$ is real). 