Spectral Transformations
  R. Lehoucq and D. Sorensen

It is well known that the iterative projection methods outlined in the previous section rapidly provide approximations to well-separated extremal eigenvalues. Quite often, however, the wanted eigenvalues may not be well separated or located in the interior of the convex hull of eigenvalues. In these situations, iterative projection methods need many steps to generate acceptable approximations, to these eigenvalues, if they converge at all. An alternative is to employ a spectral transformation of $A$ so that these poorly separated eigenvalues are transformed to well-separated extremal eigenvalues. Of course, the eigenvalues of $A$ should be easily recoverable from the eigenvalues of the transformed problem, and the transformation should be efficiently applicable in terms of computer time and storage.

The notion of well-separated (or nonclustered) eigenvalues can be roughly explained as follows. A well-separated eigenvalue $\lambda_i$ is such that $\vert\lambda_i - \lambda_j \vert > \tau \vert \lambda_n - \lambda_1\vert$ for all $j \ne i$ with $\tau \gg \epsilon_M$. For Hermitian matrices, we suppose that $\lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n$, while for non-Hermitian matrices, $\re(\lambda_1) \leq \re(\lambda_2) \leq \cdots \leq \re(\lambda_n)$.

The shift-and-invert spectral transformation (SI) is the one typically used. If $(\lambda,x)$ is an eigenpair for $A$, $Ax = \lambda x$, and $\sigma \ne \lambda$ then the shift-and-invert eigenvalue problem is

$$(A - \sigma I)^{-1} x = \nu x, \quad \mbox{where} \quad \nu = \frac{1}{\lambda - \sigma }.$$ (15)

This SI is effective for finding eigenvalues near $\sigma$ because the nearby eigenvalues $\nu_j$ of $C \equiv (A - \sigma I)^{-1}$ that are largest in magnitude correspond to the nearby eigenvalues $\lambda_j$ that are nearest to the shift $\sigma$. These transformed eigenvalues of largest magnitude are precisely the eigenvalues that are the easiest to compute. Once they are found, they may be transformed back to eigenvalues of the original problem. The direct relation is

$$\lambda_j = \sigma + \frac{1}{\nu_j},$$

and the eigenvector $x_j$ associated with $\nu_j$ in the transformed problem is also an (generalized) eigenvector of the original problem corresponding to $\lambda_j.$ Other spectral transformation techniques include the generalized Cayley transformation; see [324] for further details.

The SI is extremely effective in terms of iteration steps (that is the dimension of the subspace) and should be used whenever possible. This is particularly the case when interior eigenvalues are sought, or when the desired eigenvalues are significantly smaller in magnitude than the eigenvalues largest in magnitude, or when the desired eigenvalues are clustered.

The potential drawback of a spectral transformation is that linear systems involving $A-\sigma I$ must be solved. This can either be accomplished via a matrix factorization or with an iterative method. The user should use a sparse direct method to factor the appropriate matrix whenever feasible. If an iterative method is used for the linear system solves, the accuracy of the solutions must be commensurate with the convergence tolerance used for the eigensolver. A heuristic is that a slightly more stringent tolerance is needed for the iterative linear system solves (relative to the desired accuracy of the eigenvalue calculation). See [283,291,414] for a discussion and further references.

It is also possible to carry out the transformation in an approximate way and to work with subspaces that no longer have a Krylov structure. This is the idea behind several algorithms, including the Jacobi-Davidson method. The latter, and other methods, will also be discussed in more detail in the remainder of the book.