# Asymmetrical Lanczos method

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

```
.
```

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