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 $H$ 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 $\epsilon_D$ with $1 > \epsilon_D > \epsilon_M$, where $\epsilon_M$ is machine precision. In theory (i.e., in exact arithmetic), when $A$ 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 $k$ 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 $H$ long before small subdiagonal elements appear. This convergence is usually detected through observation of a small last component in an eigenvector $y$ of $H$. When this happens, we are able to construct an orthogonal similarity transformation of $H$ that will give an equivalent Arnoldi factorization with a slightly perturbed $H$ 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 $\theta$ has converged (meaning $\Vert Ax - x\theta\Vert < \epsilon_D$) and thought to be a member of the wanted set of eigenvalues, then we wish to declare it converged, decouple the eigenpair $(x, \theta)$, and continue to compute remaining eigenvalues with no further alteration of $x$ or $\theta$. This process is called locking.

Purging:

If a Ritz value $\theta$ has converged but is not a member of the wanted set, then we wish to decouple and remove the eigenpair $(x, \theta)$ from the current Krylov subspace spanned by the Arnoldi vectors. This process is called purging.

Techniques for this deflation were first developed in [289,294]. The scheme we present here is based an improvement developed in [420]. This scheme allows for stable and efficient deflation (or locking) of Ritz values that have converged with a specified relative accuracy of $\epsilon_D$, which may be considerably larger than machine precision $\epsilon_M$. This is particularly important when an SI is not available to accelerate convergence. Typically, in this setting the number of matrix-vector products will be large and it will be highly desirable to lock converged Ritz values at low tolerances. This will avoid the expense of the matrix-vector products that would be required to achieve an accuracy that would allow normal QR-type deflation. Also, it is very important to be able to purge converged but unwanted Ritz values. As pointed out in  [289], the forward instability of the QR bulge-chase process discovered by Parlett and Le [359] will prevent implicit restarting to be used for purging converged unwanted Ritz values.