Preconditioner

Transforms equations for numerical solution

In mathematics, preconditioning is the application of a transformation, called the preconditioner, that conditions a given problem into a form that is more suitable for numerical solving methods. Preconditioning is typically related to reducing a condition number of the problem. The preconditioned problem is then usually solved by an iterative method.

In linear algebra and numerical analysis, a preconditioner of a matrix is a matrix such that has a smaller condition number than It is also common to call the preconditioner, rather than , since itself is rarely explicitly available. In modern preconditioning, the application of , i. e., multiplication of a column vector, or a block of column vectors, by , is commonly performed in a matrix free fashion, i. e., where neither , nor (and often not even ) are explicitly available in a matrix form. Preconditioners are useful in iterative methods to solve a linear system for since the rate of convergence for most iterative linear solvers increases because the condition number of a matrix decreases as a result of preconditioning. Preconditioned iterative solvers typically outperform direct solvers, e. g., Gaussian elimination, for large, especially for sparse, matrices. Iterative solvers can be used as matrix free methods, i. e. become the only choice if the coefficient matrix is not stored explicitly, but is accessed by evaluating matrix vector products.

For a symmetric positive definite matrix the preconditioner is typically chosen to be symmetric positive definite as well. The preconditioned operator is then also symmetric positive definite, but with respect to the based scalar product. In this case, the desired effect in applying a preconditioner is to make the quadratic form of the preconditioned operator with respect to the based scalar product to be nearly spherical.

Denoting , we highlight that preconditioning is practically implemented as multiplying some vector by , i. e., computing the product In many applications, is not given as a matrix, but rather as an operator acting on the vector Some popular preconditioners, however, change with and the dependence on may not be linear. Typical examples involve using non linear iterative methods, e. g., the conjugate gradient method, as a part of the preconditioner construction. Such preconditioners may be practically very efficient, however, their behavior is hard to predict theoretically.

One interesting particular case of variable preconditioning is random preconditioning, e. g., multigrid preconditioning on random coarse grids. If used in gradient descent methods, random preconditioning can be viewed as an implementation of stochastic gradient descent and can lead to faster convergence, compared to fixed preconditioning, since it breaks the asymptotic "zig zag" pattern of the gradient descent.

The most common use of preconditioning is for iterative solution of linear systems resulting from approximations of partial differential equations. The better the approximation quality, the larger the matrix size is. In such a case, the goal of optimal preconditioning is, on the one side, to make the spectral condition number of to be bounded from above by a constant independent of the matrix size, which is called spectrally equivalent preconditioning by D'yakonov. On the other hand, the cost of application of the should ideally be proportional (also independent of the matrix size) to the cost of multiplication of by a vector.

The Jacobi preconditioner is one of the simplest forms of preconditioning, in which the preconditioner is chosen to be the diagonal of the matrix Assuming , we get It is efficient for diagonally dominant matrices It is used in analysis softwares for beam problems or 1 D problems (EX: STAAD. Pro)

The Sparse Approximate Inverse preconditioner minimises where is the Frobenius norm and is from some suitably constrained set of sparse matrices. Under the Frobenius norm, this reduces to solving numerous independent least squares problems (one for every column). The entries in must be restricted to some sparsity pattern or the problem remains as difficult and time consuming as finding the exact inverse of The method was introduced by M. J. Grote and T. Huckle together with an approach to selecting sparsity patterns.

Eigenvalue problems can be framed in several alternative ways, each leading to its own preconditioning. The traditional preconditioning is based on the so called spectral transformations. Knowing (approximately) the targeted eigenvalue, one can compute the corresponding eigenvector by solving the related homogeneous linear system, thus allowing to use preconditioning for linear system. Finally, formulating the eigenvalue problem as optimization of the Rayleigh quotient brings preconditioned optimization techniques to the scene.

By analogy with linear systems, for an eigenvalue problem one may be tempted to replace the matrix with the matrix using a preconditioner However, this makes sense only if the seeking eigenvectors of and are the same. This is the case for spectral transformations. The most popular spectral transformation is the so called shift and invert transformation, where for a given scalar , called the shift, the original eigenvalue problem is replaced with the shift and invert problem The eigenvectors are preserved, and one can solve the shift and invert problem by an iterative solver, e. g., the power iteration. This gives the Inverse iteration, which normally converges to the eigenvector, corresponding to the eigenvalue closest to the shift The Rayleigh quotient iteration is a shift and invert method with a variable shift. Spectral transformations are specific for eigenvalue problems and have no analogs for linear systems. They require accurate numerical calculation of the transformation involved, which becomes the main bottleneck for large problems.

To make a close connection to linear systems, let us suppose that the targeted eigenvalue is known (approximately). Then one can compute the corresponding eigenvector from the homogeneous linear system Using the concept of left preconditioning for linear systems, we obtain , where is the preconditioner, which we can try to solve using the Richardson iteration

====The ideal preconditioning In this case the preconditioned gradient aims closer to the point of the extrema as on the figure, which speeds up the convergence.