GMRES

CG: applies when the matrix is symmetric positive definite.

GMRES: applies to any matrix, but there is a higher computational cost. This is similar to the difference between the Lanczos process and the Arnoldi process.

GMRES is simpler than CG because fewer optimizations are possible.

“Just solve a least-squares problem.”

Norm to measure error

The key in GMRES is to change the cost function we are optimizing:

$$\Vert x-x^{(k)}{\Vert }_{?}$$

CG choice: $\Vert z{\Vert }_A=\sqrt{z^{T}Az}$

GMRES choice: $\Vert z{\Vert }_{A^{T}A}=\sqrt{z^T{A}^{T}Az}$

This norm makes more sense once we apply it:

$$\begin{array}{rl}\Vert x-x^{(k)}{\Vert }_{A^{T}A}^2& =(x-Q_{k}y{)}^T{A}^{T}A(x-Q_{k}y)\\ & =\Vert b-A{Q}_{k}y{\Vert }_2^2=\Vert r^{(k)}{\Vert }_2^2\end{array}$$

• We can now explain the acronym!
• GMRES = Generalized Minimal RESidual method.