Deflation and Stopping Rules

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:

*Locking:*-
If a Ritz value has converged
(meaning
) and thought to be a member
of the wanted set of eigenvalues, then we wish to declare
it converged, decouple the eigenpair , and continue
to compute remaining eigenvalues with no further alteration of or .
This process is called locking.
*Purging:*- If a Ritz value has converged but is not a member of the wanted set, then we wish to decouple and remove the eigenpair from the current Krylov subspace spanned by the Arnoldi vectors. This process is called purging.