Spectral Transformation

If the extreme eigenvalues are not well separated and when we want interior eigenvalues, it is greatly advantageous to replace $A$ by a shift-and-invert operator

$$C=(A-\sigma I)^{-1}\,$$ (28)

for an appropriately chosen shift $\sigma$, for instance, in the interval $\alpha \le \sigma \le \beta$, where we are interested in knowing the eigenvalues. The shift-and-invert operator $C$ has the eigenvalues

$$\theta_i=\frac{1}{\lambda_i-\sigma}\quad\mbox{or}\quad \lambda_i=\sigma+\frac{1}{\theta_i}\;,$$ (29)

and now the eigenvalues $\theta_i$ that correspond to eigenvalues $\lambda_i$ close to the shift $\sigma$ will be at the ends of the spectrum and well separated from the rest; see [162].

If we use a shift-and-invert operator, we start the algorithm by factoring

$$LDL^{\ast}=P^T(A-\sigma I)P\,,$$ (30)

using some appropriate sparse Gaussian elimination scheme. Here, $P$ is a permutation and $L$ is unit lower triangular. If there are eigenvalues $\lambda$ at both sides of the shift $\sigma$, we cannot use a scalar diagonal $D$, but we have to make a symmetric indefinite factorization, as in MA47 of Duff and Reid [141]. Here $D$ is block diagonal with one by one and two by two blocks, and we get the inertia of $A-\sigma I$ as a by-product. We can get a count of the number of eigenvalues in an interval by recording the inertia of $(A-\sigma I)$ for two values $\sigma$ at the ends of the interval. Obtaining this count is used to make sure that no multiple eigenvalues are missed. See §10.3 for further information about sparse matrix factorizations.

During the actual iteration, we use the factors $P$, $L$, and $D$, computing

$$r=P(L^{-\ast}(D^{-1}(L^{-1}(P^Tv_j))))\;,$$ (31)

in the order indicated by the parentheses, in step (5) of Algorithm 4.6.