Deflation is an important concept in the practical implementation
of the QR iteration and therefore equally important to the IRAM.
In the context of the QR iteration, deflation amounts to setting
a small subdiagonal element of the
Hessenberg matrix to zero. This is called deflation because
it splits the Hessenberg matrix into two smaller subproblems which
may be independently refined further.
However, in the context of IRAM, the usual QR deflation techniques are
not always appropriate. Additional deflation capabilities specific to
implicit restarting are needed.
It is often desirable to deflate at an accuracy
level with
,
where
is machine precision. In theory (i.e., in
exact arithmetic), when
has a multiple eigenvalue corresponding
to distinct eigenvectors, it would be
impossible for IRAM to compute more than one instance of this multiplicity.
This is because it is a ``single vector" rather than a block method.
However, in practice, there is usually little difficulty in computing
multiple eigenvalues because the method deflates itself as convergence
takes place, and roundoff usually introduces components in new eigenvector directions
in the subsequent starting vectors. Nevertheless, this can be unreliable
and miss a multiple eigenvalue. In any case, this approach typically
will require a stringent convergence tolerance to succeed in finding all
instances of a multiple eigenvalue.
It is far more efficient to deflate (i.e., lock) an approximate eigenvalue
once it has converged to a certain level of accuracy and then force
subsequent Arnoldi vectors to be orthogonal to the converged subspace.
With this capability, additional instances of a multiple eigenvalue can be
computed to the same specified accuracy without the expense of converging them
to unnecessarily high accuracy.
In the Arnoldi procedure, as with a QR iteration, it is possible
for some of the
leading subdiagonals to become small during the course of implicit
restarting. However, it is usually the case that there are converged
Ritz values appearing in the spectrum of
long before small
subdiagonal elements appear. This convergence is usually detected
through observation of a small last component in an eigenvector
of
.
When this happens, we are able to construct
an orthogonal similarity transformation of
that will give
an equivalent Arnoldi factorization with a slightly perturbed
that
does indeed have a zero subdiagonal, and this is the basis of our
deflation schemes.
In the context of IRAM, there are two types of deflation required: