Preconditioned conjugate gradient method

The conjugate gradient method is a numerical algorithm that solves a system of linear equations

${\displaystyle Ax=b.\,}$

where ${\displaystyle A}$ is symmetric [positive definite]. If the matrix ${\displaystyle A}$ is ill-conditioned, i.e. it has a large condition number ${\displaystyle \kappa (A)}$, it is often useful to use a preconditioning matrix ${\displaystyle P^{-1}}$ that is chosen such that ${\displaystyle P^{-1}\approx A^{-1}}$ and solve the system

${\displaystyle P^{-1}Ax=P^{-1}b,\,}$

instead.

To save computional time it is important to take a symmetric preconditioner. This can be Jacobi, symmetric Gauss-Seidel or Symmetric Successive Over Relaxation (SSOR).

The simplest preconditioner is a diagonal matrix that has just the diagonal elements of ${\displaystyle A}$. This is known as Jacobi preconditioning or diagonal scaling. Since diagonal matrices are trivial to invert and store in memory, a diagonal preconditioner is a good starting point. More sophisticated choices must trade-off the reduction in ${\displaystyle \kappa (A)}$, and hence faster convergence, with the time spent computing ${\displaystyle P^{-1}}$.

External links

• Preconditioned Conjugate Gradient – math-linux.com
• An Introduction to the Conjugate Gradient Method Without the Agonizing Pain by Jonathan Richard Shewchuck