Next: Basic Algorithm Up: Jacobi-Davidson Methods   G. Sleijpen Previous: Jacobi-Davidson Methods   G. Sleijpen   Contents   Index

## Basic Theory

The Jacobi-Davidson method is based on a combination of two basic principles. The first one is to apply a Galerkin approach for the eigenproblem , with respect to some given subspace spanned by an orthonormal basis . The usage of other than Krylov subspaces was suggested by Davidson [99], who also suggested specific choices, different from the ones that we will take, for the construction of orthonormal basis vectors . The Galerkin condition is

which leads to the reduced system
 (57)

where denotes the matrix with columns to . This equation has solutions . The pairs are called the Ritz values and Ritz vectors of with respect to the subspace spanned by the columns of . These Ritz pairs are approximations for eigenpairs of , and our goal is to get better approximations by a well-chosen expansion of the subspace.

At this point the other principle behind the Jacobi-Davidson approach comes into play. The idea goes back to Jacobi [241]. Suppose that we have an eigenvector approximation for an eigenvector corresponding to a given eigenvalue . Then Jacobi suggested (in the original paper for strongly diagonally dominant matrices) computing the orthogonal correction for so that

Since , we can restrict ourselves to the subspace orthogonal to . The operator restricted to that subspace is given by

and we find that satisfies the equation

In practical situations we do not know , and the obvious solution to this is to replace it by its approximation , which leads to the Jacobi-Davidson correction equation for an update :
 (58)

This correction equation is solved only approximately and its approximate solution is taken for the expansion of the subspace. This is a fundamental difference with the Krylov subspace methods; instead of selecting a subspace as powers of an operator acting on a given starting vector, we select some subspace without Krylov structure and we project the given matrix onto this subspace.

From (4.48) we conclude that , and in particular that , so that the Jacobi-Davidson correction equation represents a consistent linear system.

It can be shown that the exact solution of (4.49) leads to cubic convergence of the largest towards for increasing (similar statements can be made for the convergence towards other eigenvalues of , provided that the Ritz values are selected appropriately in each step).

In [411] it is suggested to solve equation (4.49) only approximately, for instance, by some steps of minimal residual (MINRES) [350], with an appropriate preconditioner for , if available, but in fact any approximation technique for is formally allowed, provided that the projectors are taken into account. In our templates we will present ways to approximate with Krylov subspace methods.

We will now discuss how to use preconditioning for an iterative solver like generalized minimal residual (GMRES) or conjugate gradient squared (CGS), applied to equation (4.49). Suppose that we have a left preconditioner available for the operator , for which in some sense . Since varies with the iteration count , so may the preconditioner, although it is often practical to work with the same for different values of . Of course, the preconditioner has to be restricted to the subspace orthogonal to as well, which means that we have to work with, efficiently,

This may seem unnecessarily complicated, and at first sight it also seems to involve a lot of overhead because of the projections surrounding the matrix-vector operations. But it all amounts to a handful of rather simple operations, as we will show now.

We assume that we use a Krylov solver with initial guess and with left preconditioning for the approximate solution of the correction equation (4.49). Since the starting vector is in the subspace orthogonal to , all iteration vectors for the Krylov solver will be in that space. In that subspace we have to compute the vector for a vector supplied by the Krylov solver, and

We will do this in two steps. First we compute

with since . Then, with left-preconditioning, we solve from

Since , it follows that satisfies or . The condition leads to

The vector is solved from and, likewise, is solved from . The last equation has to be solved only once in an iteration process for equation (4.49), so that effectively operations with the preconditioner are required for iterations of the linear solver. Also, a matrix-vector multiplication with the left-preconditioned operator in an iteration of the Krylov solver requires only one inner product and one vector update instead of the four actions of the projector operator . This has been worked out in the solution template, given in Algorithm 4.15. Along similar lines one can obtain an efficient template, although slightly more expensive than the left-preconditioned case, for the right-preconditioned operator. This template is described in Algorithm 4.16. For more details on preconditioning of the correction equation, see [412].

If we form an approximation for in (4.49) as , with such that and without acceleration by an iterative solver, we obtain a process which was suggested by Olsen, Jørgensen, and Simons [344].

Next: Basic Algorithm Up: Jacobi-Davidson Methods   G. Sleijpen Previous: Jacobi-Davidson Methods   G. Sleijpen   Contents   Index
Susan Blackford 2000-11-20