next up previous contents index
Next: Matrix Transformations Up: Preconditioning Techniques Previous: Introduction   Contents   Index


Inexact Methods
  K. Meerbergen and R. Morgan

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.



Subsections
next up previous contents index
Next: Matrix Transformations Up: Preconditioning Techniques Previous: Introduction   Contents   Index
Susan Blackford 2000-11-20