Large, sparse symmetric eigenvalue problems are often thought of as easier than non symmetric ones, mainly because of the good conditioning of their eigenvalues. In addition, Krylov spaces for symmetric matrices entail certain optimalities that are not present in the non symmetric case. However, the exact same reasons have allowed scientists and engineers to increase the accuracy of their models, producing very large matrices for which simple Lanczos programs are not adequate. Preconditioned eigensolvers have been in the spotlight during the last decade. As in linear systems, they target large, difficult eigenproblems, but unlike linear systems, the mechanism for applying the preconditioner could be slightly more involved.

Jacobi-Davidson is considered one of the most popular preconditioned eigenmethods. Originally, it addressed how to apply a preconditioner appropriately to the correction equation. This was a simple extension of the Davidson method. It also studied how to apply a preconditioned iterative linear solver for solving the correction equation. Today, Jacobi-Davidson is mostly associated with this inner-outer method.

Inner-outer iterative methods are potentially very powerful, if one can fine tune the inner stopping criterion. Some recent advances (EIGIFP, JDCG) suggest that for symmetric matrices we may be close to an optimal answer. Notay noticed that if the inner method iterates to convergence it would produce the inverse iteration approximation. If we could cheaply monitor the eigenvector residual during CG in the correction phase, we could stop the linear solver when the linear solver residual started to deviate from the eigenvector residual. At that point, it would be better to return to the outer method and update the Ritz values and vectors. Notay showed some impressive convergence results for his method, JDCG.

First, we improve on JDCG by extending Notay's results to the symmetric QMR of Freund and Nachtigal. The method, JDQMR, is slightly more expensive per iteration than JDCG, but it works with indefinite matrices (e.g., interior eigenvalues) and more importantly with indefinite symmetric preconditioners. In addition, it provides a smooth, monotonic convergence for the residual which facilitates a more accurate prediction of the relative rates of convergence between linear system and eigenvalue solver. Our experiments confirm the smoother convergence and show that when many iterations are required, JDQMR converges better than JDCG. The results are more pronounced without preconditioning.

Second, we explore convergence as a function of execution time and when several eigenvalues are sought. Perhaps not too surprisingly, in these cases other methods become equally effective and often better than the inner-outer JD. For example LOBPCG combines a conjugate-gradient like recurrence with subspace iteration. Its convergence is sometimes comparable to that of JDQMR for one eigenvalue, but it is usually better for more eigenvalues while being less expensive.

Yet, in one of our earlier papers, an idea similar to LOBPCG had been used to restart (Jacobi-)Davidson methods that did not employ an inner iteration. When looking for m eigenpairs, the scheme restarted with k < m+1 Ritz vectors from the last two successive iterations (a total of 2k vectors). We proved that because of closeness to the Conjugate Gradient method, the method behaves similarly to the unrestarted method. We called this method JD+k

Our experiments show that JD+k converges at least twice as fast as LOBPCG, and much faster than the inner-outer JDQMR when seeking several eigenpairs. Despite a more expensive iteration, we justify through timing experiments why JD+k is still faster than JDQMR/LOBPCG, and why JDQMR may still be the method of choice for one eigenpair, even without preconditioning.