A Brief Survey of Iterative Linear Solvers

In the context of eigenproblems it may be necessary to solve a linear system, for instance, in the following situations:

- The Jacobi-Davidson methods require the (approximate) solution of a linear correction equation.
- Inexact methods, like those discussed in Chapter 11, are based on an approximate shift-and-invert step, for which a linear system needs to be approximately solved.
- Given a good approximation for an eigenvalue, the corresponding left or right eigenvector can be computed from a linear system with the shifted matrix.

The currently most popular iterative methods belong to the class of Krylov subspace methods. These methods construct approximations for the solution from the so-called Krylov subspace. The Krylov subspace of dimension , associated with a linear system (where and may be the preconditioned values, if preconditioning is included) for a starting vector with residual vector is defined as the subspace spanned by the vectors {, , }.

The different methods can be classified as follows:

- (a)
- If is symmetric positive definite, then the
*conjugate gradient*method [226] generates, using two-term recurrences, the for which (the so-called -norm or energy norm) is minimized over all vectors in the current Krylov subspace . - (b)
- If is only symmetric but not positive definite, then
the
*Lanczos*[286] and the*MINRES*methods [350] may be considered. In MINRES, the is determined for which the 2-norm of the residual () is minimized, while the Lanczos method leads to an for which is perpendicular to the Krylov subspace. - (c)
- If is unsymmetric, it is in general not possible to determine
an optimal
with short recurrences. This was proved
in [163]. However, with short recurrences as in conjugate
gradients (and MINRES), we can compute the
, for which
(usually, one selects ). This leads to the
*bi-conjugate gradient method*[169]. A clever variant is quasi-minimal residual (QMR) [179], which has smoother convergence behavior and is more robust than bi-conjugate gradients. - (d)
- If is unsymmetric, then we can compute the , for which the residual is minimized in the Euclidean norm. This is done by the GMRES method [389]. This requires inner products at the th iteration step, as well as vector updates, which means that the iteration costs, that come in addition to operations with , grow linearly with .
- (e)
- The operations with in the bi-conjugate gradient method can be replaced by operations with itself, by using the observation that equals , where represents the inner-product computation. Since the function of the multiplications by in bi-conjugate gradient serves only to maintain the dual space to which residuals are orthogonalized, the replacement of this operator by allows us to expand the Krylov subspace and to find better approximations for virtually the same costs per iteration as for bi-conjugate gradients. This leads to so-called hybrid methods such as conjugate gradients squared [418], Bi-CGSTAB [445], Bi-CGSTAB() [409], TFQMR [174], and hybrids of QMR [78].
- (f)
- For indefinite systems it may also be effective to apply the conjugate gradient method for the normal equations . Carrying this out in a straight-forward manner may lead to numerical instabilities, because has a squared condition number. A clever and robust implementation is provided in least squares QR [351].