What are preconditioners?

Preconditioners are easy-to-compute approximate inverses of matrices, used to speed up linear solvers.

There are two approaches to solving a linear system Ax=b. One is the direct approach, for instance, computing the inverse of A. Given large linear systems, direct methods often require too much time or memory. The second approach is to use iterative methods. The term iterative methods refers to a wide range of techniques that use successive approximations to obtain increasingly more accurate solutions to a linear system.

When matrix A is positive definite, a common iterative method is Conjugate Gradients (CG). In the i-th, this method finds the vector closest to the solution in the Krylov subspace, that is the subspace spanned by the vectors b,Ab,...,Aⁱb. It turns out that the Krylov subspace often contains a good approximation of the solution, even for small i's.

The convergence rate of CG depends on the distribution of A's eigenvalues. If the eigenvalues tend to be clustered away from the origin, then convergence is rapid. If the eigenvalues are distributed more-or-less evenly and close to the origin, convergence is slow. The number of iterations needed for convergence is bounded by the square root of the conditioner number of A, multiplied by a constant.

A preconditioner is a matrix used to speed up an iterative solver. Let M be our preconditioner. Instead of solving Ax=b, we will solve the preconditioned system M^-1Ax=M^-1b. This transformation makes sense if the distribution of the eigenvalues of M^-1A is better than that of A. This generally means that M^-1A has a small condition number. Intuitively, we try to find a preconditioner such that M^-1 approximates A^-1. As a result, M^-1A approximates the identity matrix, which has a condition number of 1.

The Preconditioned Conjugate Gradients (PCG) algorithm is an algorithm which solves a linear system Ax=b by solving another linear system, one in which the coefficient matrix is M^-1/2AM^-1/2 (rather than M^-1A -- that way symmetry is preserved). It does so without having to compute either M^-1/2 or M^+1/2. PCG solves one system of the form My=z in each iteration.

When using an iterative method to solve a linear system of equations, a good choice of preconditioner can have a dramatic impact on runtime and robustness. A good preconditioner must have a variety of properties. First, the preconditioned system should converge quickly. This generally means M^-1A has a small condition number. Second, it should be easy to solve systems of the form My=z. And obviously the construction of the preconditioner should be efficient in both time and space.

The generation of good preconditioners involves as much art as science. The best preconditioners tend to be application-specific, exploiting insight into the precise problem being solved. A number of general purpose preconditioner have been developed which often work well in practice. The most widely used of these are variants on incomplete factorizations and approximate inverses. Unfortunately, these general purpose approaches tend to be poorly understood theoretically (except perhaps on model problems), and they sometimes perform badly. New ways of thinking about preconditioning are urgently needed.

Support theory is a new methodology for bounding condition numbers of preconditioned systems. To learn more about support theory, click here.