Shift Selection

There are many ways to select the shifts $\{ \mu_j \}$ that are applied by the QR steps. Virtually any explicit polynomial restart scheme could be applied through this implicit mechanism. Considerable success has been obtained with the choice of exact shifts. This selection is made by sorting the eigenvalues of $T_m$ into two disjoint sets of $k$ ``wanted" and $p$ ``unwanted" eigenvalues and using the $p$ unwanted ones as shifts. With this selection, the $p$ shift applications result in $T_k^+$ having the $k$ wanted eigenvalues as its spectrum. As convergence takes place, the subdiagonals of $T_k$ tend to zero and the most desired eigenvalue approximations appear as eigenvalues on the diagonal of the leading $k \times k$ block of $T_m$. The basis vectors $V_k$ tend to be orthogonal eigenvectors of $A$.

Examples of the ``wanted set" specification are:

the $k$ algebraically smallest eigenvalues,

the $k$ algebraically largest eigenvalues,

the $k$ eigenvalues with largest magnitude,

the $k$ eigenvalues with smallest magnitude.

When choosing between these alternatives, remember that eigenvalues in the ends of the spectrum converge first, so any choice to avoid these may lead to slow convergence. SI is recommended when seeking interior eigenvalues.

Other interesting choices of shifts $\{ \mu_j \}$ include the roots of Chebyshev polynomials [383], harmonic Ritz values [331,337,349,411], the roots of Leja polynomials [23], the roots of least squares polynomials [384], and refined shifts [244]. In particular, the Leja and harmonic Ritz values have been used to estimate the interior eigenvalues of $A$.

An alternate interpretation stems from the fact that each of these shift cycles results in the implicit application of a polynomial in $A$ of degree $p$ to the starting vector: v_1 (A) v_1 with () = _j=1^p (- _j ). The roots of this polynomial are the shifts used in the QR process and these may be selected to enhance components of the starting vector in the direction of eigenvectors corresponding to desired eigenvalues and damp the components in unwanted directions. Of course, this is desirable because it forces the starting vector into an invariant subspace associated with the desired eigenvalues. This in turn forces $r_k$ to become small, and hence convergence results. Full details may be found in [419].

There is an alternative way to apply implicit restart, thick restart, as described by Wu and Simon [463]. There an eigenvalue factorization of $T_m$ (4.20) is computed, and the part that corresponds to the wanted eigenvalues is kept as an arrow matrix and the rest is discarded. Thick restart is mathematically equivalent to exact shift IRLM, if the same choice of wanted and unwanted eigenvalues is made.