# 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

`IterativeSolvers.lobpcg`

— FunctionThe 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.

`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.

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.

`IterativeSolvers.lobpcg!`

— Function`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.

## 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]}.

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