Toward the optimal preconditioned eigensolver ABSTRACT: The preconditioned conjugate gradient method became the standard solver for extremely large linear systems with symmetric positive definite matrices of coefficients. Our ultimate goal is developing a similar optimal method for symmetric eigenproblems. We introduce a definition of algorithm optimality for symmetric eigenproblems, using a generalized Krylov subspace based on polynomials of two variables. We propose benchmarking for computing the extreme eigenpair, suggesting, as the ideal control algorithm, the standard preconditioned conjugate gradient method for finding an eigenvector as an element of the null-space of the corresponding homogeneous system of linear equations under the assumption that the eigenvalue is known. We recommend every new preconditioned eigensolver be compared with this ideal algorithm on our model test problems in terms of the speed of convergence, costs of every iterations and memory requirements.

Searching for the optimal algorithm, we describe the Locally Optimal Block Preconditioned Conjugate Gradient (LOBPCG) Method for symmetric eigenvalue problems, based on a local optimization of a three-term recurrence. Numerical results establish that our LOBPCG Method is practically as efficient as the ideal algorithm. We also show numerically that the LOBPCG Method provides approximations to first eigenpairs of about the same quality as those by the much more expensive global optimization method on the same generalized block Krylov subspace. We discuss several inner-outer iterative preconditioned eigensolvers, e.g., the inexact Jacobi-Davidson method, and show that they produce approximations in the generalized Krylov subspace. Direct numerical comparisons with 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. A revised version accepted to SIAM SISC.