Locally Optimal Block Preconditioned Conjugate Gradient (LOBPCG) is a matrix-free method for finding the largest (or smallest) eigenvalues and the corresponding eigenvectors of a symmetric positive definite generalized eigenvalue problem
which results in finding largest (or smallest) eigenpairs of
called the preconditioned residual. Without preconditioning, we set and so . An iterative method
or, in short,
is known as preconditioned steepest ascent (or descent), where the scalar is called the step size. The optimal step size can be determined by maximizing the Rayleigh quotient, i.e.,
(or in case of minimizing), in which case the method is called locally optimal. To further accelerate the convergence of the locally optimal preconditioned steepest ascent (or descent), one can add one extra vector to the two-term recurrence relation to make it three-term:
(use in case of minimizing). The maximization/minimization of the Rayleigh quotient in a 3-dimensional subspace can be performed numerically by the Rayleigh–Ritz method. As the iterations converge, the vectors and become nearly linearly dependent, making the Rayleigh–Ritz method numerically unstable in the presence of round-off errors. It is possible to substitute the vector with an explicitly computed difference making the Rayleigh–Ritz method more stable; see.
This is a single-vector version of the LOBPCG method. It is one of possible generalization of the preconditioned conjugate gradient linear solvers to the case of symmetric eigenvalue problems. Even in the trivial case and the resulting approximation with will be different from that obtained by the Lanczos algorithm, although both approximations will belong to the same Krylov subspace.
Iterating several approximate eigenvectors together in a block in a similar locally optimal fashion, gives the full block version of the LOBPCG. It allows robust computation of eigenvectors corresponding to nearly-multiple eigenvalues.
LOBPCG's inventor, Andrew Knyazev, published an implementation called Block Locally Optimal Preconditioned Eigenvalue Xolvers (BLOPEX) with interfaces to PETSc and hypre. Other implementations are available in Octave, MATLAB, ABINIT (including CUDA version), Octopus (software), PESCAN, Anasazi (Trilinos), SciPy, NGSolve, NVIDIA AmgX, and PYFEMax.
- Knyazev, Andrew V. (2001). "Toward the Optimal Preconditioned Eigensolver: Locally Optimal Block Preconditioned Conjugate Gradient Method". SIAM Journal on Scientific Computing 23 (2): 517. doi:10.1137/S1064827500366124.
- Knyazev, A. V.; Argentati, M. E.; Lashuk, I.; Ovtchinnikov, E. E. (2007). "Block Locally Optimal Preconditioned Eigenvalue Xolvers (BLOPEX) in Hypre and PETSc". SIAM Journal on Scientific Computing 29 (5): 2224. doi:10.1137/060661624.
- Yamada, S.; Imamura, T.; Machida, M. (2005). 16.447 TFlops and 159-Billion-dimensional Exact-diagonalization for Trapped Fermion-Hubbard Model on the Earth Simulator. Proc. ACM/IEEE Conference on Supercomputing (SC'05): 44. doi:10.1109/SC.2005.1. ISBN 1-59593-061-2.
- Yamada, S.; Imamura, T.; Kano, T.; Machida, M. (2006). Gordon Bell finalists I—High-performance computing for exact numerical approaches to quantum many-body problems on the earth simulator. Proc. ACM/IEEE conference on Supercomputing (SC '06). p. 47. doi:10.1145/1188455.1188504. ISBN 0769527000.
- LOBPCG code in MATLAB
- LOBPCG code in Octave
- LOBPCG code in SciPy
- LOBPCG code in Java at Google Code
- LOBPCG in Block Locally Optimal Preconditioned Eigenvalue Xolvers (BLOPEX) at Bitbucket
- LOBPCG in Block Locally Optimal Preconditioned Eigenvalue Xolvers (BLOPEX) at Google Code (retiring)