If one is searching for the eigenpair with the smallest or largest eigenvalue only, then the obvious restart approach works quite well, but often it does not do very well if one is interested in an interior eigenvalue. The problem is that the Ritz values converge monotonically towards exterior eigenvalues, and a Ritz value that is close to a target value in the interior of the spectrum may be well on its way to some other exterior eigenvalue. It may even be the case that the corresponding Ritz vector has only a small component in the direction of the desired eigenvector. It will be clear that such a Ritz vector represents a poor candidate for restart and the question is, What is a better vector for restart? One answer is given by the so-called harmonic Ritz vectors, discussed in §3.2; see also [331,349,411].
As we have seen, the Jacobi-Davidson methods generate basis vectors
for a subspace
. For the
projection of
onto this subspace we compute the vectors
. The harmonic Ritz values are inverses of the
Ritz values of
, with
respect to the subspace spanned by the
.
They can be computed without
inverting
, since a harmonic Ritz pair
satisfies
In [349] it is shown that for Hermitian the harmonic Ritz
values converge monotonically towards the smallest nonzero eigenvalues
in absolute value. Note that the harmonic Ritz values are unable to
identify a zero eigenvalue of
, since that would correspond to an
infinite eigenvalue of
. Likewise, the harmonic Ritz values for
the shifted matrix
converge monotonically towards eigenvalues
closest to the target value
. Fortunately, the
search subspace
for the shifted matrix and the unshifted
matrix coincide, which facilitates the computation of harmonic Ritz
pairs for any shift.
The harmonic Ritz vector for the shifted matrix, corresponding
to the harmonic Ritz value closest to
, can be interpreted as
maximizing a Rayleigh quotient for
. It represents
asymptotically the best information that is available for the wanted
eigenvalue, and hence it represents asymptotically the best candidate as
a starting vector after restart, provided that
.
For harmonic Ritz values, the correction equation has to take into
account the orthogonality with respect to
, and this
leads to skew projections. We can use orthogonal projections in
the following way. If
is the selected
approximation of an eigenvector, the Rayleigh quotient
leads to
the residual with smallest norm; that is, with
, we have that
for any scalar
, including the harmonic Ritz value
. Moreover, the residual
for the Rayleigh
quotient is orthogonal to
. This makes
``compatible'' with
the operator
in the correction
equation. Here
.
An algorithm for the Jacobi-Davidson method based on harmonic Ritz values and
vectors, combined with restart and deflation, is given in
Algorithm 4.19. The algorithm can be used for the computation of
a number of successive eigenvalues immediately to the right of the
target value .
To apply this algorithm we need to specify a starting vector , a
tolerance
, a target value
, and a number
that
specifies how many eigenpairs near
should be computed. The value
of
denotes the maximum dimension of the search subspace. If it
is exceeded, a restart takes place with a subspace of specified
dimension
.
On completion, the eigenvalues at the right side nearest to
are delivered. The computed eigenpairs
,
, satisfy
, where
denotes the
th column of
.
For exterior eigenvalues a simpler algorithm has been described in §4.7.3. We will now comment on some parts of the algorithm in view of our discussions in previous subsections.
The vectors are the columns of
by
matrix
and
.
Detection of all wanted eigenvalues cannot be guaranteed; see note (14) for Algorithm 4.13 and note (13) for Algorithm 4.17.