Krylov subspace method

Krylow subspace methods are iterative methods for solving large, sparsely populated linear systems of equations , such as those arising from the discretization of partial differential equations , or of eigenvalue problems . They are named after the Russian naval engineer and mathematician Alexei Nikolayevich Krylov , who defined the Krylov subspaces . The method he developed for calculating the coefficients of the characteristic polynomial no longer has much to do with the methods described here . The methods are so-called black box methods, which are characterized by simple implementation and robustness, which is why they are used widely. The procedures are almost all projection procedures .

The procedural class

The linear system of equations with the matrix is ​​given . At any approximate solution for and the residue is -th Krylov subspace of the vectors spanned subspace . ${\displaystyle \mathbf {A} x=b}$ ${\displaystyle \mathbf {A} \in \mathbb {R} ^{n\times n}}$ ${\displaystyle x_{0}}$ ${\displaystyle x}$ ${\displaystyle r_{0}=b-\mathbf {A} x_{0}}$ ${\displaystyle m}$ ${\displaystyle {\mathcal {K}}_{m}}$ ${\displaystyle r_{0},\mathbf {A} r_{0},\dots ,\mathbf {A} ^{m-1}r_{0}}$

Almost all methods now find a better approximate solution with the condition that the vector is orthogonal to all vectors of a subspace , a so-called orthogonal projection . This condition is called the Galerkin condition . ${\displaystyle x_{m}\in x_{0}+{\mathcal {K}}_{m}}$ ${\displaystyle b-\mathbf {A} x_{m}}$ ${\displaystyle {\mathcal {L}}_{m}}$

This reduces the problem to a -dimensional linear system of equations. The whole thing becomes an iterative solution method if you increase the dimension by one in each step. ${\displaystyle m}$

Special solution processes result from the specific choice of the room , as well as from the use of special properties of the matrix , which accelerates the process, but also limits its applicability. The simplest variant is to simply choose the Krylow subspace yourself again. The special thing about the method is that you only need matrix-vector multiplications and scalar products . If the matrix is ​​sparse, the matrix-vector product can be calculated quickly and the algorithm is practicable. ${\displaystyle {\mathcal {L}}_{m}}$ ${\displaystyle \mathbf {A} }$ ${\displaystyle {\mathcal {L}}_{m}}$

One example is the conjugate gradient ( CG ) method . Here is and it is intended for symmetrical , positively definite matrices. ${\displaystyle {\mathcal {L}}_{m}={\mathcal {K}}_{m}}$

So you get a variety of procedures. Much more important than choosing the specific Krylov subspace method is the choice of preconditioner . This transforms the linear system of equations equivalently, so that the solution remains unchanged, but more favorable properties for the convergence result. Crucial speed gains are to be achieved here, which means that even systems with millions of unknowns can be satisfactorily solved in a few dozen steps.

effort

The method is characterized by the fact that only matrix-vector multiplications and scalar products are required in the process. The matrix-vector multiplication only costs arithmetic operations for a sparse matrix with entries . So the total effort for iterations is still at , but with a very high constant. Accordingly, Krylow subspace methods are not suitable for fully populated matrices and only for thinly populated matrices from a certain size, in about tens of thousands of unknowns. ${\displaystyle O(n)}$ ${\displaystyle O(n)}$ ${\displaystyle m\ll n}$ ${\displaystyle O(n)}$

history

The first Krylow subspace methods were the Lanczos method published by Cornelius Lanczos in 1950 and 1952 , the Arnoldi method published in 1951 by Walter Edwin Arnoldi , and the CG method published in 1952 by Magnus Hestenes and Eduard Stiefel . Most Krylow subspace methods are even direct solvers, which reproduce the exact solution after n steps at the latest with exact arithmetic. However, the methods are unsuitable as direct solvers due to the instability of rounding errors . The benefit as an iterative solver was not yet recognized at that time and so the procedures disappeared in the drawer. Early 1970, the benefit of the CG method with preconditioning was then recognized by Reid and 1971 a compelling error analysis of the symmetric Lanczos process of Christopher Conway Paige given. This resulted in a multitude of new, better, and more stable methods such as MinRes , SymmLQ , GMRES and QMR , and entirely new Krylow subspace methods such as CGS , BiCG , BiCGSTAB and TFQMR were developed. The current classification of the Krylow subspace methods according to the QOR and QMR approaches as well as generalizations of the CG method according to the Orthores , Orthomin and Orthodir approaches began at the end of the 1970s.

In the meantime there are adapted Krylow subspace methods for nonlinear eigenvalue problems, such as the rational Krylow from Axel Ruhe and the nonlinear Arnoldi from Heinrich Voss. For some time there have also been methods that use Krylow subspace methods to solve nonlinear systems of equations in the inner loop of a Newton method , subsumed under the heading Newton-Krylow methods or, if the preconditioner is mentioned, for example Newton-Krylow-Schwarz methods.

Alphabetical list of common Krylow subspace methods

• Arnoldi method for the eigenvalue approximation
• BiCG , the CG method for non-SPD matrices
• BiCGSTAB , stabilization of CGS
• BiCGSTAB (ell) , stabilization of CGS
• BiCGSTABTFQMR , the approach behind TFQMR applied to BiCGSTAB
• BiOres , a variant of the BiCG process
• BiOmin , a variant of the BiCG process
• BiOdir , a variant of the BiCG process
• CG , for the approximate solution of linear systems of equations
• CGNE , CG method based on the normal equations, variant 1
• CGNR , CG method based on the normal equations, variant 2
• CGS method , squared BiCG recursion
• FOM , for the approximate solution of linear systems of equations
• GMRES , for the approximate solution of linear systems of equations
• Hessenberg method for the eigenvalue approximation
• (Stabilized) Induced Dimension Reduction , short term recursion and method class for linear and eigenvalue solvers
• Lanczos method , for the eigenvalue approximation
• MinRes , for the approximate solution of linear systems of equations
• Orthores, Orthomin and Orthodir, generalizations of the CG method
• Ores , a variant of the CG process
• Omin , a variant of the CG method
• Odir , a variant of the CG process
• Power method, oldest method for eigenvalue approximation
• QMR , for the approximate solution of linear systems of equations
• Richardson iteration , if interpreted appropriately
• SymmLQ , for the approximate solution of linear systems of equations
• TFQMR , for the approximate solution of linear systems of equations

literature

• A. Meister: Numerics of linear systems of equations , 2nd edition, Vieweg 2005, ISBN 3-528-13135-7

• Y. Saad: Iterative Methods for Sparse Linear Systems , 2nd edition, SIAM Society for Industrial & Applied Mathematics 2003, ISBN 0-89871-534-2

Web links

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

• Templates for the Solution of Linear Systems