Preconditioned Lanczos Methods

The preconditioned Lanczos method was suggested by Scott [397], though with $T=I$, and was analyzed by Knyazev [264,265]. It is based on the following idea of inner/outer iterations, which we describe here for the pencil $B - \mu A$.

Let parameter $\mu$ be fixed. We consider the following auxiliary eigenvalue problem:

$$T (B- \mu A)v= \nu v.$$ (284)

If $\mu = \mu_1,$ then there exists a zero eigenvalue $\nu$, and the corresponding eigenvector of (11.14) is also the eigenvector of the original pencil $B - \mu A$ corresponding to $\mu_1.$ This zero eigenvalue is the maximal eigenvalue of the matrix $T (B- \mu A)$ and is separated from the rest of the spectrum of $T (B- \mu A)$, which is negative. Thus, it can be computed using standard polynomial methods applied to $T (B- \mu A)$, in particular, by the Lanczos method. We note that the separation, which determines the speed of convergence, depends on the quality of the preconditioner $T$; see [264,265].

In the method, we choose some initial value of parameter $\mu= \mu^{(0)}$, and then use a few Lanczos inner iterations to solve for the largest eigenvalue of (11.14). Under our assumption that the preconditioner $T$ is symmetric positive definite, the matrix $T (B- \mu A)$ is symmetric with respect to the $T^{-1}$-based scalar product, therefore, the classical Lanczos method can be used with this scalar product; see §4.4. The new value of $\mu = \mu^{(1)}$ is then calculated as the Rayleigh quotient for the original pencil of the most recent vector iterate of the inner iterations. This vector also serves as an initial guess for the next cycle of inner iteration. Such inner/outer iterative method clearly fits our definition of preconditioned eigensolvers.

We present the single-vector version of the method for the pencil $B - \mu A$ in Algorithm 11.7.

Asymptotic quadratic convergence of the outer iterations for a fully converged inner iteration process was proved by Scott [397]. This does not guarantee much, of course, for the convergence of the method with limited number of inner iterations. An explicit convergence rate estimate for an arbitrary number of inner iterations was established in [264,265]. It shows that, first, the method converges at least linearly for any fixed number of inner iterations, e.g., only even one, and, second, a slow, but unlimited, increase of the number of inner iterations during the process improves the convergence rate estimate, averaged with regard to the number of inner iterations.

The preconditioned Lanczos method may converge faster than the preconditioned steepest descent/ascent method. Moreover, if the standard three-term recurrence without reorthogonalization is used in inner iterations of the Lanczos method, then the computational costs for each iteration are not much more than for the preconditioned steepest descent/ascent method.

The main disadvantage is that in the Lanczos process a $T^{-1}$-based scalar product is required, so that it should be easy to compute vectors $T^{-1}x$. For some preconditioners, e.g., domain decomposition-based ones, it may be possible to compute only $Tx$ efficiently (which is also necessary), but not $T^{-1}x$.

In such a situation, however, we may still construct a Krylov subspace for the operator $T(B - \mu^{(i)}A)$ and project the operator $B - \mu A$ onto this subspace using the Rayleigh-Ritz procedure. Schematically:

$$\begin{tabular}{c} $\mu (x^{(i+1)}) = {\rm max}_{ x \in {\ca... ..., \ \ldots, [T(B- \mu^{(i)} A)]^{l_i}x^{(i)} \}$, \end{tabular}$$ (285)

where $l_i$ is the number of inner iteration steps for the $i$th outer iteration step.

This leads to the method of Algorithm 11.8 that can be obtained from Algorithm 11.7 by modifying lines (4) and (5):

The method was suggested in [264,265] and then was rediscovered in [336]. If only one inner iteration is used, the method is identical to the preconditioned steepest descent/ascent Algorithm 11.6.

Because of the similarities with the preconditioned Lanczos process much of the convergence theory and the main conclusions thereof carry over to this process as well; for details see [264,265]. The preconditioned projection Algorithm 11.8 converges somewhat faster than the preconditioned Lanczos Algorithm 11.7 with the same number of inner iterations. However, the standard three-term recurrence can now only be used to compute the basis of the Krylov subspace. To implement the Rayleigh-Ritz method we need to store all the vectors of the basis and explicitly compute all scalar products. This makes the cost of computing projection matrices in the Rayleigh-Ritz method higher and significantly increases storage requirements, unless restarts are used.