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 generalized eigenvalue problem
A x = λ B x , {\displaystyle Ax=\lambda Bx,}
for a given pair ( A , B ) {\displaystyle (A,B)} of complex Hermitian or real symmetric matrices, where the matrix B {\displaystyle B} is also assumed positive-definite.
Background Kantorovich in 1948 proposed calculating the smallest eigenvalue λ 1 {\displaystyle \lambda _{1}} of a symmetric matrix A {\displaystyle A} by steepest descent using a direction r = A x − λ ( x ) x {\displaystyle r=Ax-\lambda (x)x} of a scaled gradient of a Rayleigh quotient λ ( x ) = ⟨ x , A x ⟩ / ⟨ x , x ⟩ {\displaystyle \lambda (x)=\langle x,Ax\rangle /\langle x,x\rangle } in a scalar product ⟨ x , y ⟩ = x T y {\displaystyle \langle x,y\rangle =x^{\mathsf {T}}y} , with the step size computed by minimizing the Rayleigh quotient in the linear span of the vectors x {\displaystyle x} and r {\displaystyle r} , i.e. in a locally optimal manner. Samokish proposed applying a preconditioner T {\displaystyle T} to the residual vector r {\displaystyle r} to generate the preconditioned direction w = T r {\displaystyle w=Tr} and derived asymptotic, as x {\displaystyle x} approaches the eigenvector, convergence rate bounds. D'yakonov suggested spectrally equivalent preconditioning and derived non-asymptotic convergence rate bounds. Block locally optimal multi-step steepest descent for eigenvalue problems was described in. Local minimization of the Rayleigh quotient on the subspace spanned by the current approximation, the current residual and the previous approximation, as well as its block version, appeared in. The preconditioned version was analyzed in and.
Main features Source:
Matrix-free, i.e. does not require storing the coefficient matrix explicitly, but can access the matrix by evaluating matrix-vector products. Factorization-free, i.e. does not require any matrix decomposition even for a generalized eigenvalue problem. The costs per iteration and the memory use are competitive with those of the Lanczos method, computing a single extreme eigenpair of a symmetric matrix. Linear convergence is theoretically guaranteed and practically observed. Accelerated convergence due to direct preconditioning, in contrast to the Lanczos method, including variable and non-symmetric as well as fixed and positive definite preconditioning. Allows trivial incorporation of efficient domain decomposition and multigrid techniques via preconditioning. Warm starts and computes an approximation to the eigenvector on every iteration. More numerically stable compared to the Lanczos method, and can operate in low-precision computer arithmetic. Easy to implement, with many versions already appeared. Blocking allows utilizing highly efficient matrix-matrix operations, e.g., BLAS 3. The block size can be tuned to balance convergence speed vs. computer costs of orthogonalizations and the Rayleigh-Ritz method on every iteration.
Algorithm
Single-vector version
Preliminaries: Gradient descent for eigenvalue problems The method performs an iterative maximization (or minimization) of the generalized Rayleigh quotient
ρ ( x ) := ρ ( A , B ; x ) := x T A x x T B x , {\displaystyle \rho (x):=\rho (A,B;x):={\frac {x^{\mathsf {T}}Ax}{x^{\mathsf {T}}Bx}},}
which results in finding largest (or smallest) eigenpairs of A x = λ B x . {\displaystyle Ax=\lambda Bx.}
The direction of the steepest ascent, which is the gradient, of the generalized Rayleigh quotient is positively proportional to the vector
r := A x − ρ ( x ) B x , {\displaystyle r:=Ax-\rho (x)Bx,}
called the eigenvector residual. If a preconditioner T {\displaystyle T} is available, it is applied to the residual and gives the vector
w := T r , {\displaystyle w:=Tr,}
called the preconditioned residual. Without preconditioning, we set T := I {\displaystyle T:=I} and so w := r {\displaystyle w:=r} . An iterative method
… excerpt ends here. Continue reading the full article.
