Preconditioning the Conjugate Gradients algorithm

We follow some of the strategies outlined earlier and consider a symmetric preconditioning method. Assume we have a matrix $C$ such that $CA{C}^T$ has good convergence properties for CG, e.g., a smaller condition number.

$CA{C}^T$ is SPD if $C$ is non-singular. This is a key property to ensure that CG applies.

We now consider solving the modified linear system using CG:

$$CA{C}^{T}y=Cb,x=C^{T}y.$$

Here is a possible implementation that follows directly the CG algorithm:

$$\begin{array}{rl}{q}^{(k)}& =CA{C}^T{p}^{(k)}\\ {\mu }_k& =\frac{\Vert s^{(k-1)}{\Vert }_2^2}{(p^{(k)}{)}^T{q}^{(k)}}\\ y^{(k)}& =y^{(k-1)}+{\mu }_k{p}^{(k)}\\ s^{(k)}& =s^{(k-1)}-{\mu }_k{q}^{(k)}\\ {\tau }_k& =\frac{\Vert s^{(k)}{\Vert }_2^2}{\Vert s^{(k-1)}{\Vert }_2^2}\\ p^{(k+1)}& =s^{(k)}+{\tau }_k{p}^{(k)}\end{array}$$

This implementation is cumbersome because of the need to multiply by $C$ and $C^T$. Typically, preconditioners are of the form $M=C^{T}C$, and we consider $MA$ as the new matrix. With this form, we are only required to be able to multiply by $M$, not $C$ and $C^T$.

The preconditioned CG algorithm allows getting rid of $C$ in favor of $M$ only. This is a significant simplification in the implementation.

PCG is equivalent to the algorithm written above but does the algebra slightly differently to avoid the appearance of $C$.

Krylov subspace

The reason why $C$ can be avoided can be traced back to how the Krylov subspace is constructed.

When using $CA{C}^T$, in the Krylov subspace, we use powers of $CA{C}^T$ and we get:

$$(CA{C}^T{)}^k=CA(C^{T}CA{)}^{k-1}{C}^T=CA(MA{)}^{k-1}{C}^T$$

We can make this even cleaner with

$$C^T(CA{C}^T{)}^{k}Cb=C^{T}CA(MA{)}^{k-1}{C}^{T}Cb=(MA{)}^{k}Mb$$

Only $M$ appears!

In terms of the Krylov subspace, we can write:

$$\mathcal{K}(CA{C}^T,Cb,k)=\text{span}\{Cb,CA{C}^{T}Cb,(CA{C}^T{)}^{2}Cb,\dots ,(CA{C}^T{)}^{k-1}Cb\}$$

Multiply by $C^T$ and we get a sequence with $MA$ and $b$ only:

$$C^T\mathcal{K}(CA{C}^T,Cb,k)=\text{span}\{Mb,MAMb,(MA{)}^{2}Mb,\dots ,(MA{)}^{k-1}Mb\}$$

This seems promising. We can construct a Krylov subspace with $M$ only.

Note that since we require $M=C^{T}C$, with $C$ non-singular, the preconditioner $M$ must be SPD.