LOBPCG

# Locally optimal block preconditioned conjugate gradient (LOBPCG)

Solves the generalized eigenproblem \$Ax = λBx\$ approximately where \$A\$ and \$B\$ are Hermitian linear maps, and \$B\$ is positive definite. \$B\$ is taken to be the identity by default. It can find the smallest (or largest) `k` eigenvalues and their corresponding eigenvectors which are B-orthonormal. It also admits a preconditioner and a "constraints" matrix `C`, such that the algorithm returns the smallest (or largest) eigenvalues associated with the eigenvectors in the nullspace of `C'B`.

## Usage

The Locally Optimal Block Preconditioned Conjugate Gradient Method (LOBPCG)

Finds the `nev` extremal eigenvalues and their corresponding eigenvectors satisfying `AX = λBX`.

`A` and `B` may be generic types but `Base.mul!(C, AorB, X)` must be defined for vectors and strided matrices `X` and `C`. `size(A, i::Int)` and `eltype(A)` must also be defined for `A`.

``lobpcg(A, [B,] largest, nev; kwargs...) -> results``

Arguments

• `A`: linear operator;
• `B`: linear operator;
• `largest`: `true` if largest eigenvalues are desired and false if smallest;
• `nev`: number of eigenvalues desired.

Keywords

• `log::Bool`: default is `false`; if `true`, `results.trace` will store iterations states; if `false` only `results.trace` will be empty;

• `P`: preconditioner of residual vectors, must overload `ldiv!`;

• `C`: constraint to deflate the residual and solution vectors orthogonal to a subspace; must overload `mul!`;

• `maxiter`: maximum number of iterations; default is 200;

• `tol::Real`: tolerance to which residual vector norms must be under.

Output

• `results`: a `LOBPCGResults` struct. `r.λ` and `r.X` store the eigenvalues and eigenvectors.
source
``lobpcg(A, [B,] largest, X0; kwargs...) -> results``

Arguments

• `A`: linear operator;
• `B`: linear operator;
• `largest`: `true` if largest eigenvalues are desired and false if smallest;
• `X0`: Initial guess, will not be modified. The number of columns is the number of eigenvectors desired.

Keywords

• `not_zeros`: default is `false`. If `true`, `X0` will be assumed to not have any all-zeros column.

• `log::Bool`: default is `false`; if `true`, `results.trace` will store iterations states; if `false` only `results.trace` will be empty;

• `P`: preconditioner of residual vectors, must overload `ldiv!`;

• `C`: constraint to deflate the residual and solution vectors orthogonal to a subspace; must overload `mul!`;

• `maxiter`: maximum number of iterations; default is 200;

• `tol::Real`: tolerance to which residual vector norms must be under.

Output

• `results`: a `LOBPCGResults` struct. `r.λ` and `r.X` store the eigenvalues and eigenvectors.
source

lobpcg(A, [B,] largest, X0, nev; kwargs...) -> results

Arguments

• `A`: linear operator;
• `B`: linear operator;
• `largest`: `true` if largest eigenvalues are desired and false if smallest;
• `X0`: block vectors such that the eigenvalues will be found size(X0, 2) at a time; the columns are also used to initialize the first batch of Ritz vectors;
• `nev`: number of eigenvalues desired.

Keywords

• `log::Bool`: default is `false`; if `true`, `results.trace` will store iterations states; if `false` only `results.trace` will be empty;

• `P`: preconditioner of residual vectors, must overload `ldiv!`;

• `C`: constraint to deflate the residual and solution vectors orthogonal to a subspace; must overload `mul!`;

• `maxiter`: maximum number of iterations; default is 200;

• `tol::Real`: tolerance to which residual vector norms must be under.

Output

• `results`: a `LOBPCGResults` struct. `r.λ` and `r.X` store the eigenvalues and eigenvectors.
source
``lobpcg!(iterator::LOBPCGIterator; kwargs...) -> results``

Arguments

• `iterator::LOBPCGIterator`: a struct having all the variables required for the LOBPCG algorithm.

Keywords

• `not_zeros`: default is `false`. If `true`, the initial Ritz vectors will be assumed to not have any all-zeros column.

• `log::Bool`: default is `false`; if `true`, `results.trace` will store iterations states; if `false` only `results.trace` will be empty;

• `maxiter`: maximum number of iterations; default is 200;

• `tol::Real`: tolerance to which residual vector norms must be under.

Output

• `results`: a `LOBPCGResults` struct. `r.λ` and `r.X` store the eigenvalues and eigenvectors.
source

## Implementation Details

A `LOBPCGIterator` is created to pre-allocate all the memory required by the method using the constructor `LOBPCGIterator(A, B, largest, X, P, C)` where `A` and `B` are the matrices from the generalized eigenvalue problem, `largest` indicates if the problem is a maximum or minimum eigenvalue problem, `X` is the initial eigenbasis, randomly sampled if not input, where `size(X, 2)` is the block size `bs`. `P` is the preconditioner, `nothing` by default, and `C` is the constraints matrix. The desired `k` eigenvalues are found `bs` at a time.

## References

Implementation is based on [Knyazev1993] and [Scipy].

[Knyazev1993]

Andrew V. Knyazev. "Toward the Optimal Preconditioned Eigensolver: Locally Optimal Block Preconditioned Conjugate Gradient Method" SIAM Journal on Scientific Computing, 23(2):517–541 2001.