In numerical mathematics , the unsymmetrical Lanczos method is, on the one hand, an iterative method for the approximate determination of some eigenvalues and possibly their eigenvectors of a matrix . On the other hand, it is also the basis for some algorithms for the approximate solution of systems of equations , namely the biconjugate gradient method, also known as the BiCG method for short .
The projection on a tri-diagonal shape
The algorithm uses a short recursion to generate matrices and , the columns of which form biorthogonal bases of the Krylow spaces and .
Given a square matrix . Now two (unnormalized) start vectors and are required, mostly good candidates exist from previous calculations or random vectors are chosen.
The algorithm is as follows:
- Set ,
- for do
- end for
The oblique projection of the matrix onto a tridiagonal matrix formed from the scalars has the asymmetrical tridiagonal structure
The above algorithm contains freedom in the choice of and , since in line three only the product of the two quantities is included. Common choices are
Both options have their advantages and disadvantages.
The eigenvalues of the tridiagonal matrix are then used as approximations for the eigenvalues of . The approximations for eigenvectors are given by the extended eigenvectors . Due to the relationship with a (crooked) Galerkin projection, the pairs are often referred to as scratch pairs even in the non-symmetrical case .
Refinements and enhancements
This original method based on a three-way recursion breaks down if applies. If (at least) one of the two vectors equals zero, or , then the associated Krylow subspace is an invariant subspace of and all eigenvalues of , the Ritz values, are also eigenvalues of . If, however, and and , the process can no longer be continued using a three-fold recursion .
Approximate solution of systems of equations
In the context of systems of equations , the zeroth residual is taken as the start vector .
The prolonged solution of the tridiagonal system , where denotes the first unit vector of the length , is taken as an approximate solution . This approach is known as the quasi-orthogonal residual approach , or QOR for short . If you use the QOR approach, depending on the details, a variant of the well-known BiCG method emerges.
A second approach is based on an extended tridiagonal matrix and is known as the quasi-minimal residual approach , or QMR for short . If you use the QMR approach, the well-known method of the same name of the quasi-minimal residuals, QMR for short, comes out.
Multiplication by and in the original algorithm is too expensive , especially if it is known only as a black box. Sonneveld was the first to implement a method based on Lanczos recursion, which only works with multiplications . The class of these methods is known in English under the name Lanczos-type product methods , LTPM for short , coined by Martin H. Gutknecht .
The method given by Sonneveld is known as the method of the squared (bi) conjugate gradient, in English conjugate gradient squared , or CGS for short . Further representatives of this group are CGS2 , shifted CGS , BiCGSTAB , BiCGSTAB (ell) , GPBiCG , TFQMR and QMRCGSTAB .
- Andreas Meister: Numerics of linear systems of equations. An introduction to modern procedures . 2nd edition Vieweg, Wiesbaden 2005, ISBN 3-528-13135-7 (with MATLAB implementations by Christoph Vömel).