ABSTRACT:

Many applied and engineering problems, e.g., in structural mechanics, design of nuclear reactors, ocean modeling, and quantum chemistry, lead, after simplifications and an appropriate approximation of original partial differential equations, to extremely large and ill-conditioned linear systems with symmetric positive definite matrices of coefficients and similar symmetric eigenvalue problems. The preconditioned conjugate gradient method became the standard solver for such linear systems. Our ultimate goal is developing an analogous optimal method for eigenproblems. Ideally, we want to be able to compute an eigenvector of interest at the same cost as that of solving a linear system of equations, using the same preconditioner. That would allow, in particular, a simple adaptation for eigenproblems of available domain decomposition based and multigrid preconditioners for linear systems.

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 is practically 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 one of them, the inexact Jacobi-Davidson method, show that our LOBPCG method is more robust and converges almost two times faster. Finally, we show numerically that the LOBPCG method is robust with respect to variable preconditioning.

A MATLAB code of the LOBPCG method and the Preconditioned Eigensolvers Benchmarking are available at http://math.ucdenver.edu/~aknyazev/software/CG/

The talk is mostly based on the paper: "Toward the Optimal Preconditioned Eigensolver: Locally Optimal Block Preconditioned Conjugate Gradient Method." Published as a technical report UCD-CCM 149, 2000, at the Center for Computational Mathematics, University of Colorado Denver, see
http://math.ucdenver.edu/ccmreports/rep149.ps.gz.
A revised version accepted to SIAM SISC.