Next: Deflation and Restart Up: Jacobi-Davidson Method  G. Sleijpen and Previous: Jacobi-Davidson Method  G. Sleijpen and   Contents   Index

## Basic Theory

As for the GHEP, we want to avoid transformation of to a standard eigenproblem. This would require the solution of some linear system, involving and/or , per iteration step. Furthermore, for stability reasons we want to work with orthonormal transformations, and for this reason our goal is to compute Schur vectors for the pencil , rather than eigenvectors. This leads to a generalization of the Jacobi-Davidson algorithm, in which we compute a partial Schur form for the pencil. This algorithm can be interpreted as a subspace iteration variant of the QZ algorithm. A consequence of this approach is that we have to work with search and test spaces that are different.

With , the generalized eigenproblem is equivalent to the eigenproblem

 (221)

and we denote a generalized eigenvalue of the matrix pair as a pair . This approach is preferred, because underflow or overflow for in finite precision arithmetic may occur when and/or are zero or close to zero, in which case the pair is still well defined [328], [425, Chap. VI], [376].

A partial generalized Schur form of dimension for a matrix pair is the decomposition

 (222)

where and are orthogonal by matrices and and are upper triangular by matrices. A column of is referred to as a generalized Schur vector, and we refer to a pair , with as a generalized Schur pair. It follows that if is a generalized eigenpair of then is a generalized eigenpair of .

We will now describe a Jacobi-Davidson method for the generalized eigenproblem (8.8). From the relations (8.9) we conclude that

which suggests that we should follow a Petrov-Galerkin condition for the construction of reduced systems. In each step the approximate eigenvector is selected from a search subspace . We require that the residual is orthogonal to some other well-chosen test subspace :
 (223)

Both subspaces are of the same dimension, say . Equation (8.10) leads to the projected eigenproblem
 (224)

The pencil can be reduced by the QZ algorithm (see §8.2) to generalized Schur form (note that this is an -dimensional problem). This leads to orthogonal by matrices and and upper triangular by matrices and , such that
 (225)

The decomposition can be reordered such that the first column of and the -entries of and represent the wanted Petrov solution [172]. With and , , the Petrov vector is defined as for the associated generalized Petrov value . In our algorithm we will construct orthogonal matrices and , so that also . With the decomposition in (8.12), we construct an approximate partial generalized Schur form (cf. (8.9)): approximates a , and approximates the associated . Since (cf. (8.9)), this suggests to choose such that coincides with . With the weights and we can influence the convergence of the Petrov values. If we want eigenpair approximations for eigenvalues close to a target , then the choice

is very effective [172], especially if we want to compute eigenvalues in the interior of the spectrum of . We will call the Petrov approximations for this choice the harmonic Petrov eigenpairs. The Jacobi-Davidson correction equation for the component for the pencil becomes
 (226)

with and . It can be shown that if (8.13) is solved exactly, the convergence to the generalized eigenvalue will be quadratic; see [408, Theorem 3.2]. Usually, this correction equation is solved only approximately, for instance, with a (preconditioned) iterative solver. The obtained vector is used for the expansion of and is used for the expansion of . For both spaces we work with orthonormal bases. Therefore, the new columns are orthonormalized with respect to the current basis by a modified Gram-Schmidt orthogonalization process (see §4.7.1).

It can be shown that, with the above choices for and ,

 (227)

The relation between the partial generalized Schur form for the given large problem and the complete generalized Schur form for the reduced problem (8.11) via right vectors () is similar to the relation via left vectors (). This can also be exploited for restarts.

Next: Deflation and Restart Up: Jacobi-Davidson Method  G. Sleijpen and Previous: Jacobi-Davidson Method  G. Sleijpen and   Contents   Index
Susan Blackford 2000-11-20