Eigenvector/Null-Space Purification

   With these observations in hand, it is possible to see the virtue of using ${\bf M}$-Arnoldi on . After k-steps of ${\bf M}$-Arnoldi,

Introducing the similarity transformation gives

where and . Partitioning and consistent with the blocking of gives

Moreover, the side condition holds, so that in exact arithmetic a zero eigenvalue should not appear as a converged Ritz value of . This argument shows that ${\bf M}$-Arnoldi on is at the same time doing -Arnoldi on while avoiding convergence to zero eigenvalues.

Round-off error due to finite precision arithmetic will cloud the situation, as usual. It is clear that the goal is to prevent components in from corrupting the vectors Thus to begin, the starting vector should be of the form If a final approximate eigenvector has components in they may be purged by replacing and then normalizing. To see the effect of this, note that

and all components in which are of the form will have been purged. This final application of may be done implicitly in two ways. One is to note that if with then and the approximate eigenvector is replaced with the improved approximation where . This correction was originally suggested by Ericsson and Ruhe [13] as a mean of performing a formal step of the power method with The residual error of the computed Ritz vector with respect to the original   problem is

where Keeping in mind that under the spectral transformation is usually quite large, this estimate indicates even greater accuracy than expected from the usual estimate. This is the purification used in ARPACK.

Another recent suggestion due to Meerbergen and Spence is to use implicit restarting with a zero shift [31]. Recall that implicit restarting with zero shifts is equivalent to starting the ${\bf M}$-Arnoldi process with a starting vector of and all the resulting Ritz vectors will be multiplied by as well. After applying the implicit shifts to , the leading submatrix of order will provide the updated Ritz values. No additional explicit matrix-vector products with are required.

The ability to apply zero shifts (i.e. to multiply by implicitly) is very important when has zero eigenvalues. If then

Thus, in order to completely eradicate components from one must multiply by where is equal to the dimension of the largest Jordan block corresponding to a zero eigenvalue of . Eigenvector purification by implicit restarting may be incorporated into ARPACK at a future date.

Spectral transformations were studied extensively by Ericsson and Ruhe [13] and the first eigenvector purification strategy was developed in [34]. Shift and invert techniques play an essential role in the block Lanczos code   developed by Grimes, Lewis, and Simon and the many nuances of this technique in practical applications are discussed thoroughly in [18]. The development presented here and the eigenvector purification through implicit restarting is due to Meerbergen and Spence [31].