LOBPCG

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

for a given pair of complex Hermitian or real symmetric matrices, where the matrix is also assumed positive-definite.

Algorithm

The method performs an iterative maximization (or minimization) of the generalized Rayleigh quotient

which results in finding largest (or smallest) eigenpairs of

The direction of the steepest ascent, which is the gradient, of the generalized Rayleigh quotient is positively proportional to the vector

called the eigenvector residual. If a preconditioner is available, it is applied to the residual giving vector

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.[1]

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.

General software implementations

LOBPCG's inventor, Andrew Knyazev, published an implementation called Block Locally Optimal Preconditioned Eigenvalue Xolvers (BLOPEX) with interfaces to PETSc and hypre.[2] Other implementations are available in, e.g., Octave, MATLAB, Java, Anasazi (Trilinos), SLEPc, SciPy, and MAGMA.[3]

Applications

Material Sciences

LOBPCG is implemented in ABINIT (including CUDA version) and Octopus. It has been used for multi-billion size matrices by Gordon Bell Prize finalists, on the Earth Simulator supercomputer in Japan.[4][5] Recent implementations include TTPY,[6] Platypus‐QM,[7] and MFDn.[8]

Maxwell's equations

LOBPCG is one of core eigenvalue solvers in PYFEMax, NGSolve, and MFEM.

Data Mining

Software package Megaman uses LOBPCG to scale manifold learning algorithms to large data sets.[9]

References

  1. ↑ 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.
  2. ↑ 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.
  3. ↑ Anzt, Hartwig; Tomov, Stanimir; Dongarra, Jack (2015). "Accelerating the LOBPCG method on GPUs using a blocked sparse matrix vector product". Proceedings of the Symposium on High Performance Computing (HPC '15). Society for Computer Simulation International, San Diego, CA, USA: 75–82.
  4. ↑ 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). p. 44. doi:10.1109/SC.2005.1. ISBN 1-59593-061-2.
  5. ↑ 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.
  6. ↑ Rakhuba, Maxim; Oseledets, Ivan (2016). "Calculating vibrational spectra of molecules using tensor train decomposition". J. Chem. Phys. 145 (145): 124101. Bibcode:2016JChPh.145l4101R. doi:10.1063/1.4962420.
  7. ↑ Takano, Yu; Nakata, Kazuto; Yonezawa, Yasushige; Nakamura, Haruki (2016). "Development of massive multilevel molecular dynamics simulation program, platypus (PLATform for dYnamic protein unified simulation), for the elucidation of protein functions". J. Comput. Chem. 37 (12): 1125–1132. doi:10.1002/jcc.24318.
  8. ↑ Shao, Meiyue; et al. (2016). "Accelerating Nuclear Configuration Interaction Calculations through a Preconditioned Block Iterative Eigensolver". arXiv:1609.01689Freely accessible [cs.NA].
  9. ↑ McQueen, James; et al. (2016). "Megaman: Scalable Manifold Learning in Python". Journal of Machine Learning Research. 17 (148): 1–5.

External links

This article is issued from Wikipedia - version of the 11/7/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.