Preconditioning

The convergence of both CG and GMRES depends on the condition number of the matrix and the distribution of the eigenvalues. Convergence improves if the matrix is “closer” to the identity or has clustered eigenvalues and its eigenbasis is well-conditioned.

Convergence of the Conjugate Gradients, Convergence of GMRES

Goal of preconditioner

Preconditioners should be easy to apply and should improve the convergence of iterative methods.

The eigenvalues of the preconditioned system should be clustered and lead to fewer iterations in CG/GMRES/MINRES.

3 types of preconditioners

There are three main ways to precondition a linear system $Ax=b$.

• Left preconditioning: $(M_{1}A)x=M_{1}b$
• Right preconditioning: $(A{M}_2)z=b,$ $x=M_{2}z$
• Symmetric preconditioning: $(M_{1}A{M}_2)z=M_{1}b,$ $x=M_{2}z$

Symmetric preconditioning is required for CG because we need to maintain the SPD property. This is the case for MINRES as well. More specifically, we need to use

$$M_{1}A{M}_2$$

with $M_1=C$ and $M_2=C^T$. The preconditioned system must be constructed in a symmetric way as

$$CA{C}^T.$$

Examples of preconditioners

• (Block) diagonal matrix = Jacobi; $M^{-1}=D$
• Gauss-Seidel: $M^{-1}=D-L$
• (Symmetric) Successive Over-Relaxation
• Incomplete LU and Cholesky
• Multigrid
• Fast solvers with low-rank compression steps