Preconditioning

In numerical mathematics , preconditioning describes a technique with which a problem is reshaped in such a way that the solution is retained, but positive properties such as better condition or faster convergence result for the selected numerical solution method .

The most common form of preconditioning is linear , in which a linear system of equations is converted equivalent. This type of preconditioning is used in particular when solving the system of equations using the Krylow subspace method . Another important form arises from multiplying the time derivative term of a partial differential equation by a nonlinear preconditioning. The stationary solution of the equation is retained here. ${\displaystyle Ax=b}$

Linear preconditioning

Here, one distinguishes between Linksvorkonditionierung, wherein the system of equations from the left with a regular matrix is multiplied: and Rechtsvorkonditionierung, wherein the system of equations with is released. The preconditioner should approximate the inverse of with the least possible effort. In principle, any iterative equation solving method such as the Jacobi or the Gauss-Seidel method can be used as a preconditioner; the matrix for the preconditioning is the inverse of the matrix referred to in the article splitting method . ${\displaystyle Ax=b}$ ${\displaystyle MAx=Mb}$ ${\displaystyle AMy=b}$ ${\displaystyle y=M^{-1}x}$ ${\displaystyle A}$ ${\displaystyle M}$ ${\displaystyle B^{-1}}$ ${\displaystyle B}$

A simple example of a preconditioner is equilibration , i.e. the scaling of the rows or columns of the equation system with individual factors so that all rows or columns of the matrix then have the same norm .

In the context of Krylow subspace methods such as the CG method , it is beneficial if the system matrix has a low condition or, in particular, a “good” eigenvalue distribution . This is where the main application of preconditioners can be found, as the speed of convergence of Krylow subspace methods can be significantly improved in this way.

In addition to the iterative methods already mentioned above, incomplete LU decompositions , called ILU decompositions , are of particular interest. Using the Gaussian algorithm, these calculate an error-prone decomposition of the system matrix , in which only defined elements are calculated in order to save time and memory. ${\displaystyle A}$

Since the 1990s , multilevel methods such as geometric and algebraic multigrid methods have become more and more important.

Nonlinear preconditioners

The calculation of stationary solutions of a partial differential equation can be made more efficient by means of nonlinear preconditioning. To do this, the time derivative is multiplied by a preconditioner, so the time goes slower or faster for certain cells or variables. This is mostly done to get around the CFL condition with stiff problems.

literature

• A. Meister: Numerics of linear systems of equations , Vieweg 1999, ISBN 3-528-03135-2
• Y. Saad: Iterative Methods for Sparse Linear Systems , 2nd edition, SIAM Society for Industrial & Applied Mathematics 2003, ISBN 0-898-71534-2

Web links

• Y. Saad: Iterative Methods for Sparse Linear Systems , 1st edition, PWS 1996
• Templates for the Solution of Linear Systems