Davidson Method

As mentioned, Algorithm 11.1 does not allow updates of the zero of the Cayley transform without a complete restart. We now describe the Davidson method, which by contrast updates the zero in each iteration.

The Davidson method [99] was developed to solve quantum chemistry problems in which the matrices have diagonal elements that are both large and varying in magnitude. It was originally derived as a perturbation method. Given an approximate eigenvector, a correction is developed. In [335], the Davidson method was viewed as a diagonal preconditioning method and was generalized for other preconditioners. We now give an algorithm. The vector $w_j$ is a correction to the approximate eigenvector $y$. The preconditioner is left unspecified, but for Davidson's original method, the choice is $M=(D-\theta I)^{-1}.$

We next discuss the asymptotic convergence of the Davidson method. Observe that if $\theta$ and $M$ were fixed, the Davidson method would develop a Krylov subspace generated with the operator $M^{-1}(A-\theta B)$. So once a Ritz pair begins to converge to an eigenpair, say $(\lambda,x)$, then the subspace generated from that point is approximately the same as a Krylov subspace generated by $T_{\mathrm{IC}} \equiv M^{-1}(A-\lambda B)$. $T_{\mathrm{IC}}$ has the correct eigenvector, namely $x$, and the corresponding eigenvalue of $T_{\mathrm{IC}}$ is 0. If the other eigenvalues of $T_{\mathrm{IC}}$ are compressed around $1$ by the preconditioning, then $0$ will be well separated and convergence rapid.

An important question is whether in practice the spectrum of $T_{\mathrm{IC}}$ is really an improvement over that of the original eigenvalue problem. There is potential, because in the best case, where $M=(A-\mu B)$, we then have the exact Cayley transformation. Also, we know that in the iterative solution of linear equations, spectra are improved by preconditioning. On the other hand, preconditioning of eigenvalue problems is probably tougher than for linear equations, because asymptotically the singular matrix $(A-\lambda B)$ is being approximated. This matrix is also indefinite if $\lambda$ is not an exterior eigenvalue. We will look at two examples of how preconditioning can work for eigenvalue problems.