Methods with Preconditioned Inner Iterations

We note that there is no analog of the inverse power method in our class of preconditioned eigensolvers, as it would require exact solving linear systems with the matrix $B - \alpha A$. However, if such systems are solved using a preconditioned iterative method as inner iterations, then the method of inner/outer iterations falls into the class of preconditioned eigensolvers. As an example, we consider here the most straightforward version of the RQI, applied to the pencil $B - \mu A$; see §4.3.

It is common to use MINRES as a choice of the inner iterative solver, as the system matrix $T(B - \mu^{(i)}A)$ is indefinite. When only a fixed number of inner iterations is used, we cannot assume that the equation $(B - \mu^{(i)}A) x = A x^{(i)}$ is solved any accurately, therefore, well-known convergence properties of the RQIs, like cubic convergence, cannot be used directly to establish convergence of the actual inner/outer iterative method. Similarly, the standard perturbation theory cannot be easily applied unless an assumption is made that the number of inner steps is large enough.

The matrix $B - \mu^{(i)}A$ of the equation is ill-conditioned not only because $A$ is ill-conditioned, but also because $\mu^{(i)}$ is getting closer to an eigenvalue of the pencil $B - \mu A$. It is common to try to improve the condition number of the matrix by projecting out the subspace ${\rm span}\{ x^{(i)} \},$ using regularization or/and choosing an indefinite preconditioner $T$. It is not evident, however, whether an improvement of convergence of inner iterations is beneficial to convergence of the actual inner/outer iterative method with only a few inner steps.

There are several similar methods with analogous properties, e.g., different versions of Newton's method for finding eigenvectors as stationary vectors of the Rayleigh quotient (e.g., [461,468]) or truncated rational Krylov methods (e.g., [378,291]) or inexact homotopy methods (e.g., [309,235,469,310]); see also the previous section.

The Jacobi-Davidson method [411], described in §5.6 for a generalized symmetric eigenproblem, is one of the most famous in this class. The inexact Jacobi-Davidson method with preconditioned system solver as inner iteration does satisfy our definition of a preconditioned eigensolver.

The convergence behavior of such methods with a small number of inner iterations is not well understood.