An unfortunate aspect of the Lanczos or Arnoldi procedure is that
there is no way to determine in advance how many steps will be needed
to determine the eigenvalues of interest within a specified accuracy.
The eigeninformation obtained through this process is completely
determined by the choice of the starting vector . Unless there is a
very fortuitous choice of
, eigeninformation
of interest probably will not appear until
gets very large.
Clearly, it becomes intractable to maintain numerical orthogonality of
.
Extensive storage will be required, and repeatedly finding the eigensystem
of
also becomes expensive at a cost of
floating point operations.
The obvious need to control this cost has motivated the
development of restarting schemes. Restarting means replacing
the starting vector with an ``improved" starting vector
and
then computing a new Arnoldi factorization with the new vector.
The structure of
serves
as a guide: Our goal is to iteratively force
to be a linear
combination of eigenvectors of interest. In theory,
will vanish
if
is a nontrivial linear combination of
eigenvectors of
.
However, a more general and, in fact,
a better numerical strategy, is to force the starting vector to
be a linear combination of Schur vectors that span the desired
invariant subspace.
The need for restarting was recognized early on by Karush [258] soon after the appearance of the original algorithm of Lanczos [285]. Subsequently, there were developments by Paige [347], Cullum and Donath [89], and Golub and Underwood [197]. More recently, a restarting scheme for eigenvalue computation was proposed by Saad based upon the polynomial acceleration scheme originally introduced by Manteuffel [316] for the iterative solution of linear systems. All of these schemes are explicit in the sense that a new starting vector is produced by some process, and then an entirely new Arnoldi factorization is constructed.
There is another approach to restarting that
offers a more efficient and numerically stable formulation. This approach,
called implicit restarting, is a technique for
combining the implicitly shifted QR scheme with a -step Arnoldi or
Lanczos factorization to obtain a truncated
form of the implicitly shifted QR iteration.
The numerical difficulties and storage problems
normally associated with Arnoldi and Lanczos procedures are avoided.
The algorithm is capable of computing a few (
) eigenvalues with
user-specified features such as
largest real part or largest magnitude
using
storage. The computed Schur basis vectors for the
desired
-dimensional eigenspace are numerically orthogonal to working
precision.
Implicit restarting provides a means to extract interesting
information from large Krylov subspaces while avoiding the
storage and numerical difficulties associated with the standard approach.
It does this by continually compressing the interesting information
into a fixed-size -dimensional subspace. This is accomplished
through the implicitly shifted QR mechanism. An
Arnoldi factorization of length
,
A V_m = V_m H_m + f_m e_m^ ,
is compressed to a factorization of length
that retains
the eigeninformation of interest. This is accomplished using
QR steps to apply
shifts implicitly. The first stage of
this shift process results in
A V_m^+ = V_m^+ H_m^+ + f_m e_m^ Q ,
where
,
, and
Each
is the orthogonal matrix
associated with the shift
used during the shifted QR algorithm.
Because of the Hessenberg structure of
the matrices
, it turns out that the first
entries of the vector
are zero.
This implies that the leading
columns in equation (7.13)
remain in an Arnoldi relation. Equating the first
columns on both sides of (7.13) provides an
updated
-step Arnoldi factorization
A V_k^+ = V_k^+ H_k^+ + f_k^+ e_k^ ,
with an updated residual of the
form
.
Using this as a starting point it is possible to apply
additional steps
of the Arnoldi procedure to return to the original
-step form.
A template for computing a -step Arnoldi
factorization with implicit restart is given in Algorithm 7.7.
We will now describe some implementation details, referring to the respective phases in Algorithm 7.7.
Examples of the ``wanted set" specification are
There are many ways to select the shifts that are applied by
the QR steps. Virtually any explicit polynomial restarting 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.
Other interesting strategies 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 .