Asymmetrical Lanczos method

from Wikipedia, the free encyclopedia

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:

  1. Set ,
  2. for do
  3. end for

The oblique projection of the matrix onto a tridiagonal matrix formed from the scalars has the asymmetrical tridiagonal structure

  .

Implementation details

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

  • and
  • and .

Both options have their advantages and disadvantages.

Eigenvalue approximations

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 .

QOR

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.

QMR

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.

LTPM

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 .

literature

  • 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).