MINRES

The GMRES algorithm becomes more efficient when $A$ is symmetric. This leads to the MINRES algorithm. The initial steps of MINRES are similar to those of GMRES.

In MINRES, we also aim to minimize $\Vert r^{(k)}{\Vert }_2$. The primary distinction between GMRES and MINRES is analogous to the difference between the Arnoldi and Lanczos processes.

Recall that, following Lanczos, $AQ=QT$ where $T$ is tri-diagonal.

We get

$$A{Q}_k=Q_{k+1}{Q}_{k+1}^{T}A{Q}_k=Q_{k+1}{\underline{T}}_k$$

${\underline{T}}_k$ has size $(k+1)\times k$ and is “symmetric” tri-diagonal.

As before, the quantity we want to minimize becomes

$$\Vert b-A{Q}_k{y}^{(k)}{\Vert }_2=\Vert {\beta }_0{Q}_{k+1}{e}_1-Q_{k+1}{\underline{T}}_k{y}^{(k)}{\Vert }_2=\Vert {\beta }_0{e}_1-{\underline{T}}_k{y}^{(k)}{\Vert }_2$$

As before, we use Givens rotations

$$G_k^T\cdots G_1^T{\underline{T}}_k=\left(\begin{array}{c}{R}_k\\ 0\end{array}\right)$$

Since ${\underline{T}}_k$ is tri-diagonal, $R_k$ is upper triangular with only two upper diagonals.

As in GMRES, we then solve the least-squares problem using the $G_k$s and $R_k$.

Because of the tri-diagonal structure of ${\underline{T}}_k$ and the structure of $R_k$ with only two upper diagonals, we can efficiently transition from step $k-1$ to $k$ in MINRES with a time cost per iteration of $O(\mathrm{nnz}+n)$ instead of $O(\mathrm{nnz}+kn)$.

This is the same cost as CG but for general symmetric matrices instead of SPD.

The efficient implementation of this algorithm is the MINRES algorithm of Paige and Saunders.

When $A$ is symmetric positive definite, we get an error bound similar to CG

$$\Vert r^{(k)}{\Vert }_2\le 2\Vert r^{(0)}{\Vert }_2(\frac{\sqrt{\kappa }-1}{\sqrt{\kappa }+1}{)}^k$$