Implicit Restart

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.

**(1)**- Choose the initial starting vector , normalize and compute an
initial -step Arnoldi factorization. Ideally, for eigenvalue
calculations, one should attempt to construct a that is dominant
in eigenvector directions of interest. If there is a sequence of closely
related eigenvalue problems, this vector should be taken as a linear
combination of the eigenvectors (or Schur vectors) of interest from
the previous problem. In the absence of any other considerations, a random
vector is a reasonable choice.
**(3)**- A Ritz pair is ``converged" if
where and is ``wanted.'' Upon convergence, this pair
should be deflated. See the discussion of deflation in
§7.6.6.
**(4)**- Shift selection: The shifts are selected with respect
to the user's ``wanted set" specification and the current and perhaps
past information about the spectrum of . A successful strategy
has been to sort the eigenvalues of into a ``wanted set"
and an
``unwanted set"
and take the latter
as the selected set of shifts. This is called the
*exact shift*strategy. Other strategies are discussed below.Examples of the ``wanted set" specification are

- the eigenvalues with largest real part,
- the eigenvalues with largest magnitude,
- the eigenvalues with smallest real part,
- the eigenvalues with smallest magnitude.

**(6)-(10)**- Apply steps of the shifted QR iteration to using the
as shifts. This should be
done using the implicitly shifted QR variant.
If exact shifts are used,
then
should be zero on completion
of the steps of QR, and the leading submatrix
should have
as its eigenvalues.
**(12)**- When exact shifts are used, then the properties mentioned in (6)-(10)
are usually approximately true in finite precision. However, they
might not be achieved due to rounding errors. Therefore, it is
important to include both terms
in the update of the residual vector
, even though the term
should be zero in exact arithmetic.
Note, with exact shifts, the
updated and will provide a new -step Arnoldi
factorization with Ritz values and vectors that are the best
approximations to the user specification that have been produced so
far.
**(14)**- This step requires a slight modification of the Arnoldi factorization discussed previously. It simply begins with step of the usual scheme.

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 .