Numerical solution of extremely large and ill conditioned eigenvalue problems is attracting a growing attention recently as such problems are of major importance in applications. They arise typically as discretization of continuous models described by systems of partial differential equations. For such problems, preconditioned matrix-free eigensolvers are especially effective as the stiffness and the mass matrices do not need to be assembled, but instead can be only accessed through functions of the corresponding vector-matrix products.
While the mainstream research in the area introduces preconditioning in eigenvalue solvers using preconditioned inner iterations for solving linear systems with shift-and-invert matrices, our approach is to incorporate preconditioning directly into Krylov-based iterations. This results in simple, robust, and efficient algorithms, in many preliminary numerical comparisons superior to inner-outer schemes commonly used at present, e.g., to the celebrated inexact Jacobi-Davidson methods.
Searching for the optimal eigensolver, we describe the Locally Optimal Block Preconditioned Conjugate Gradient (LOBPCG) method for symmetric eigenvalue problems, based on a local Rayleigh-Ritz optimization of a three-term recurrence. LOBPCG can be viewed as a nonlinear conjugate gradient method of minimization of the Rayleigh quotient, which takes advantage of the optimality of the Rayleigh-Ritz procedure.
Numerical results establish that our LOBPCG method may practically be as efficient as the best possible algorithm on the whole class of preconditioned eigensolvers. We discuss several competitors, namely, some inner-outer iterative preconditioned eigensolvers. Direct numerical comparisons with two of them, the inexact Jacobi-Davidson methods JDCG and JDQR, show that our LOBPCG method is faster. A rigorous theoretical explanation of excellent convergence of the LOBPCG remains challenging and needs innovative mathematical ideas. The best presently known theoretical convergence rate estimate is proved in 2001 in an extensive four-parts paper, but it still does not capture some important convergence properties of the LOBPCG.
A MATLAB code of the LOBPCG method and the Preconditioned Eigensolvers Benchmarking are available at http://www-math.cudenver.edu/~aknyazev/software/CG/
The talk is partially based on the papers: