** Next:** Lanczos Method in GEMV
** Up:** Implicitly Restarted Lanczos Method
** Previous:** Implicit Restart
** Contents**
** Index**

##

Shift Selection

There are many ways to select the shifts that are
applied by
the QR steps. Virtually any explicit polynomial restart scheme could
be applied through this implicit mechanism. Considerable success
has been obtained with the choice of *exact shifts*. This selection is
made by sorting the eigenvalues of into two disjoint sets
of ``wanted" and ``unwanted" eigenvalues and using the
unwanted ones as shifts. With this selection, the shift applications
result in having the wanted eigenvalues as its spectrum.
As convergence takes place, the subdiagonals of tend to zero
and the most desired eigenvalue approximations appear as eigenvalues
on the diagonal of the leading block of .
The basis vectors tend to be orthogonal eigenvectors of .
Examples of the ``wanted set" specification are:

- the algebraically smallest eigenvalues,
- the algebraically largest eigenvalues,
- the eigenvalues with largest magnitude,
- the eigenvalues with smallest magnitude.

When choosing between these alternatives, remember that eigenvalues
in the ends of the spectrum converge first, so any choice to
avoid these may lead to slow convergence. SI
is recommended when seeking interior eigenvalues.
Other interesting choices of shifts
include the roots of Chebyshev
polynomials [383], harmonic Ritz
values [331,337,349,411], the roots of Leja
polynomials [23], the roots of least squares
polynomials [384], and refined shifts [244]. In
particular, the Leja and harmonic Ritz values have been used to
estimate the interior eigenvalues of .

An alternate interpretation stems from the fact that
each of these shift cycles results in the implicit application of a
polynomial in of degree to the starting vector:
v_1 (A) v_1 with () = _j=1^p (- _j ).
The roots of this polynomial are the shifts used in
the QR process and these may be selected to
enhance components of the starting vector in the direction of eigenvectors
corresponding to desired eigenvalues and damp the components in unwanted
directions. Of course, this is desirable because it forces
the starting vector into an invariant subspace associated with the
desired eigenvalues. This in turn forces to become small, and hence
convergence results. Full details may be found in [419].

There is an alternative way to apply implicit restart,
*thick restart*, as described by Wu and Simon [463].
There an eigenvalue factorization of (4.20) is
computed, and the part that corresponds to the *wanted*
eigenvalues is kept as an arrow matrix and the rest is discarded.
Thick restart is mathematically
equivalent to exact shift IRLM, if the same choice of wanted and
unwanted eigenvalues is made.

** Next:** Lanczos Method in GEMV
** Up:** Implicitly Restarted Lanczos Method
** Previous:** Implicit Restart
** Contents**
** Index**
Susan Blackford
2000-11-20