Numerical analysis Eigenvalue computations Proposition

LOBPCG

Builds on Symmetric matrix Positive definite matrix Rayleigh quotient Preconditioner Eigenvalue Min-max theorem

Statement

Let $A, B \in \R^{n \times n}$ be symmetric with $B$ positive definite, and let $\lambda_1 \le \cdots \le \lambda_n$ be the eigenvalues of the pencil $A x = \lambda B x$ . Let $T \in \R^{n \times n}$ be symmetric positive definite (the preconditioner), and let $\rho(x) = x^T A x / x^T B x$ be the Rayleigh quotient for $x \ne 0$ . Consider the single-vector locally optimal block preconditioned conjugate gradient method (LOBPCG). It starts from $x_0 \ne 0$ , and for $k \ge 0$ it sets $r_k = A x_k - \rho(x_k) B x_k, \qquad w_k = T r_k, \qquad S_k = \mathrm{span}\set{x_k, w_k, x_{k-1}}$ with $x_{-1}$ omitted for $k = 0$ . The next iterate $x_{k+1}$ is a vector that minimizes $\rho$ over $S_k \setminus \set{0}$ , computed by the Rayleigh–Ritz method on $S_k$ . Then for every $k$ :

$\lambda_1 \le \rho(x_{k+1}) \le \rho(x_k)$ ;
$\rho(x_{k+1}) \le \min_{t \in \R} \rho(x_k + t w_k)$ , so each step is at least as good as one step of preconditioned steepest descent with the optimal step length;
if $r_k = 0$ , then $x_k$ is an eigenvector and $\rho(x_k)$ is an eigenvalue of the pencil.

Remarks

Parts 1 and 2 hold because $x_k$ and every $x_k + t w_k$ lie in $S_k$ , over which $x_{k+1}$ minimizes $\rho$ ; the lower bound $\lambda_1$ is the min-max theorem for the pencil. The Rayleigh–Ritz step reduces to a generalized eigenvalue problem of size at most $3$ , the projections of $A$ and $B$ onto $S_k$ . The original method uses a direction $p_k$ , a combination of $w_{k-1}$ and $p_{k-1}$ , in place of $x_{k-1}$ ; the span $S_k$ is the same, and $p_k$ gives a better conditioned basis.

The block version iterates a block of $m$ vectors and approximates the $m$ smallest eigenvalues, with Rayleigh–Ritz on a subspace of dimension at most $3m$ . Since LOBPCG improves on preconditioned steepest descent, the convergence bounds of preconditioned inverse iteration (Knyazev and Neymeyr) apply to it. Example: with $T = I$ , $B = I$ and $x_{-1}$ dropped, the method becomes steepest descent for the Rayleigh quotient, since $r_k$ is a multiple of the gradient of $\rho$ at $x_k$ .

Going deeper

For a student

LOBPCG was introduced by Andrew Knyazev in 2001. It needs only products with $A$ , $B$ and $T$ , so it suits large sparse problems such as discretized PDE eigenproblems. There a good preconditioner, for example multigrid, makes the convergence nearly independent of the mesh size. Compared with the Lanczos algorithm, it uses a preconditioner directly and keeps a fixed small memory, at the price of solving a small dense eigenproblem at each step.

Tag	`P1ECPTAG8F`
URI	`m2://P1ECPTAG8F`
Kind	statement, proposition
Writing	W0 stub
MSC	65F15, 65F08
Status	This copy of the site has no build data. Run `m2 status P1ECPTAG8F`.
About	Eigenvalue algorithm
Uses	Symmetric matrix, Positive definite matrix, Rayleigh quotient, Preconditioner, Eigenvalue, Min-max theorem
Same as	Wikidata Q6459462 Wikipedia LOBPCG

Markdown · JSON · Edit on GitHub

What this page needs for W1

an inventory row: the row of the inventory that the node accounts for (0 of 1)
a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.