Inexact Methods

The spectral transformation Lanczos method for the Hermitian
eigenvalue
problem (HEP) and the shift-and-invert Arnoldi method for the non-Hermitian
eigenvalue
problem (NHEP) require the solution of linear systems.
Usually, direct methods are employed because one can take advantage of
one
factorization for several back transformations.
However, when the use of a direct solver becomes prohibitive, iterative
solution
methods must be used.
Direct methods usually deliver a small residual norm, while the residual
norm
depends on a tolerance in an iterative method.
An iterative method becomes more expensive when a lower residual
tolerance is used.
Therefore, it is advantageous not to solve the linear system very
accurately when
an iterative linear system solver is used.
For this reason, we call the spectral transformation eigenvalue solvers
exact when direct methods are used and inexact when iterative methods are
used.
The aim of this section is the study of the use of *inexact* linear
system solvers in the spectral transformation.

We start from the shift-and-invert Arnoldi method and gradually move towards the (Jacobi) Davidson method and inexact rational Krylov method. First, in §11.2.1, we recall the (exact) matrix transformations used and give their main properties. In §11.2.2, we introduce the notion of inexact transformation [323] and explain its importance. In §11.2.3 and §11.2.4, we give some results for the Rayleigh-Ritz procedure with inexact transformations. This includes results for nonsymmetric problems (Arnoldi [323], Davidson [332]) and symmetric problems (Lanczos [336], Davidson [335,88]) and the Jacobi-Davidson method. We can also use the matrix recurrence relation of the rational Krylov method [291] for computing eigenvalues, even when linear systems are solved inaccurately. This is studied in §11.2.7.

- Matrix Transformations
- Inexact Matrix Transformations
- Arnoldi Method with Inexact Cayley Transform
- Davidson Method
- Jacobi-Davidson Method with Cayley Transform
- Preconditioned Lanczos Method
- Inexact Rational Krylov Method
- Inexact Shift-and-Invert