Chapter 11

The Jacobi-Davidson Method

The Lanczos and Arnoldi methods are very e ective to compute extremal eigenvalues provided these are well separated from the rest of the spectrum. Lanczos and Arnoldi methods combined with a shift-and-invert sprectral transformation are also e cient to compute eigenvalues in the vicinity of the shift σ. In this case it is necessary to solve a system of equation

(A − σI)x = y, or (A − σM)x = y,

respectively, in each iteration step. These systems have to be solved very accurately since otherwise the Krylov or Arnoldi relation does not hold anymore. In most cases the matrix A − σI (or A − σM) is LU or Cholesky factored. The Jacobi–Davidson (JD) algorithm is particularly attractive if this factorization is not feasible [11].

11.1The Davidson algorithm

Let v1, . . . , vm be a set of orthonormal vectors, spanning the search space R(Vm) with Vm = [v1, . . . , vm]. In the Galerkin approach we are looking for vectors s Fm such that the Galerkin condition holds,

This immediately leads the the (small) eigenvalue problem

with solutions (ϑ(jm), s(jm)), j = 1, . . . , m. ϑ(jm) is called a Ritz value and Vms(jm) is called a Ritz vector. In the sequel we omit the superscript m for readability. The dimension of the search space should become evident from the context.

Let us consider, say, the Ritz value ϑj , its Ritz vector uj = Vmsj and their residual rj = Auj − ϑj uj . Often we are looking for the largest or smallest eigenvalue of A in which case j = 1 or j = m, respectively. The question immediately arises how we can improve (ϑj , uj ) if krj k is still large. It is straightforward to try to find a better approximate eigenpair by expanding the search space. Davidson, in his original paper [2], suggested to compute a vector t from

199