Preconditioned Lanczos Method

Suppose that $A$ and $B$ are symmetric and that we have a positive definite preconditioner $M$ for $A - \mu B$, i.e., $M \approx A - \mu B$. We can use the Arnoldi method applied to $M^{-1} (A-\nu B)$ for computing eigenvalues near $\mu$. (Again, we use a Ritz value $\theta$ as zero.) This leads to the recurrence relation

$$M^{-1} (A - \nu B) V_k = V_k H_k + f_k e_k^T \ .$$

Since $M$ is positive definite, we have that $x^{\ast} M y$ is a valid inner product. When we use the $M$ inner product, $x^{\ast} M y$, in the Arnoldi method rather than the standard one, $x^{\ast}y$, we have $V_k^{\ast} M V_k = I$ and $V_k^{\ast} M f_k = 0$, so $H_k = V_k^{\ast} (A-\nu B) V_k$ is a symmetric matrix. This implies that the Arnoldi method with the $M$ inner product reduces to the Lanczos method with $M$ inner product applied to the nonsymmetric matrix $M^{-1} (A-\nu B)$. From earlier discussions, we conclude that the preconditioned Lanczos method with $M$ inner product has similar convergence behavior as the spectral transformation Lanczos method applied to a perturbed problem.

Let $(\zeta,z)$ satisfy $H_k z = \zeta z$ and define the Ritz vector $x = V_k z$. This vector is obtained from the Lanczos (Arnoldi) recurrence relation, so not from a Galerkin projection. The Ritz value, on the other hand, can be computed via the Rayleigh quotient, i.e.,

$$\begin{eqnarray*} \theta & = & x^{\ast} A x / x^{\ast} B x \\ & = & \nu + x^{\... ...ast} H_k z / x^{\ast} B x \\ & = & \nu + \zeta / x^{\ast} B x, \end{eqnarray*}$$

which is cheap to compute, e.g. when $B$ is a diagonal matrix.

Recall that the Lanczos recurrence relation for the inexact Cayley transform $T_{\mathrm{IC}} = M^{-1} (A - \nu B)$ is

$$T_{\mathrm{IC}} V_k - V_k H_k = f_k e_k^T \ .$$

The recurrence relation can also be written in the form

$$T_{\mathrm{C}} V_k - V_k H_k = f_k e_k^T + (T_{\mathrm{C}} - T_{\mathrm{IC}}) V_k.$$

We know that for a Ritz pair $(x, \theta)$, $(T_{\mathrm{C}} - T_{\mathrm{IC}}) x$ can be small, when $\theta \approx \nu$. So, if $x$ is close to an eigenvector of $T_{\mathrm{IC}}$ and if $\theta$ is close to $\nu$, then $x$ is close to an eigenvector of $T_{\mathrm{C}}$ and so the Ritz value $\theta$ is close to an eigenvalue of $Ax = \lambda Bx$.

Morgan and Scott [336] proved the convergence for the following algorithm, for computing eigenvalues of $Ax = \lambda x$, i.e., with $B=I$.

Note that if $\mu=\nu$, then the preconditioner must not be a too-good approximation to $A - \mu B$; otherwise $T_{\mathrm{IC}} \approx I$. The value of $k$ may differ for each $l$. Morgan and Scott suggest the stopping test $-\zeta_l > \Vert T_{\mathrm{IC}}^{(l)} x_l - \zeta_l x_l\Vert$, which is cheap within the Lanczos method. It is shown in [336] that if both $M_l$ and $M_l^{-1}$ are uniformly bounded in norm, $\theta_l$ converges to an eigenvalue of $A$. Moreover, the asymptotic convergence is quadratic.