Closer to the optimal preconditioned eigensolver

Andrew Knyazev

Center for Computational Biology,
University of Colorado at Denver
P.O. Box 173364, Campus Box 170, Denver, CO 80217-3364


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 gradientmethod of minimization of the Rayleigh quotient, which takes advantage of the optimality of theRayleigh-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 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:
A.V. Knyazev, "Toward the Optimal Preconditioned Eigensolver: Locally Optimal Block Preconditioned Conjugate Gradient Method."
SIAM Journal on Scientific Computing 23 (2001), no. 2, pp. 517-541.
Andrew Knyazev and Klaus Neymeyr, " A geometric theory for preconditioned inverse iteration. III: A short and sharp convergence estimate for generalized eigenvalue problems." To appear in Linear Algebra and Its Applications, 2002.
Andrew Knyazev and Klaus Neymeyr, " Efficient solution of symmetric eigenvalue problems using multigrid preconditioners in the locally optimal block conjugate gradient method." To appear in Copper Mountain Multigrid issue of ETNA, 2002.