Locally Optimal Block Preconditioned Conjugate Gradient

Compute a few extreme eigenpairs of a large Hermitian-definite problem by repeatedly Rayleigh–Ritz optimizing a block over current Ritz vectors, preconditioned eigen-residuals, and compressed prior directions.

Version

v2 · 2026-09-06 · History

Domain-specific #

2203

Origin domain

numerical linear algebra

Subdomain

iterative eigenvalue methods

Aliases

LOBPCG

Core Idea

Locally Optimal Block Preconditioned Conjugate Gradient (LOBPCG) is a short-recurrence iterative eigensolver for a few smallest or largest eigenpairs of a real symmetric or complex Hermitian generalized problem

\[ A X=B X\Lambda, \qquad A=A^*,\quad B=B^*>0. \]

The standard problem is the special case \(B=I\). The word definite refers to the positive-definite metric supplied by \(B\); the left operator \(A\) need not itself be positive definite merely for the generalized Hermitian problem to be well formed.

Suppose the current \(n\times m\) block \(X_k\) contains approximations to \(m\) desired eigenvectors and has been made \(B\)-orthonormal. A Rayleigh–Ritz calculation in \(\operatorname{range}(X_k)\) supplies Ritz values \(\Theta_k\), and the block eigen-residual is

\[ R_k=A X_k-BX_k\Theta_k. \]

Apply a preconditioner to obtain \(W_k=T_kR_k\). After initialization, retain a block \(P_k\) that compresses useful directions from the preceding update. LOBPCG chooses the next Ritz block by solving the projected generalized eigenproblem on

\[ \mathcal S_k =\operatorname{span}\{X_k,W_k,P_k\}. \]

For the smallest eigenpairs, this is local minimization of the block Rayleigh quotient—or equivalently the trace under a \(B\)-orthonormality constraint—on the current short trial subspace. For the largest eigenpairs, the opposite end of the projected spectrum is selected. The originating paper describes this as local optimization of a three-term block recurrence.^[1]

Every modifier in the name carries an obligation. Locally optimal means the combination coefficients come from Rayleigh–Ritz optimization rather than a fixed step length. Block means several approximate eigenvectors, residuals, and directions are advanced together, not merely that one vector uses vectorized arithmetic. Preconditioned means residual corrections are shaped by a problem-aware operator before they enter the trial space. Conjugate-gradient names the retained short-memory direction mechanism; it does not change the task into solving a known linear system \(Ax=b\).

At the first iteration \(P_0\) is empty, so the search begins in \(\operatorname{span}\{X_0,W_0\}\). Thereafter the \([X,W,P]\) basis has at most \(3m\) columns before constraints, locking, or rank loss reduce it. A stable implementation does not simply insert nearly duplicate successive approximations into this basis: as convergence proceeds, residuals shrink and current and prior vectors approach dependence. Robust basis selection, \(B\)-orthogonalization, rank detection, and a trustworthy projected solve are part of making the exact-arithmetic recurrence work in finite precision.^[2]

LOBPCG is matrix-free in the practical sense that it can consume actions of \(A\), \(B\), and \(T_k\) on blocks without storing or factoring a dense coefficient matrix. It is not operator-free or cost-free: operator actions, orthogonalization, communication, and the dense projected eigensolve remain. Its stable identity is therefore the joint package of a Hermitian-definite extreme-eigenpair target, block Ritz state, preconditioned residual expansion, compressed prior directions, and locally optimal Rayleigh–Ritz extraction.

Structural Signature

Sig role-phrases:

• the Hermitian-definite eigenproblem — a standard or generalized pencil \((A,B)\) with \(A=A^*\) and \(B=B^*>0\)
• the extreme spectral target — a declared block of the smallest or largest eigenpairs rather than an arbitrary interior region or full decomposition
• the current Ritz block — \(B\)-orthonormal columns \(X_k\) approximating the desired invariant subspace
• the block Rayleigh readout — Ritz values \(\Theta_k\) obtained by projecting the pencil onto the current or expanded subspace
• the eigen-residual block — \(R_k=AX_k-BX_k\Theta_k\), whose columns measure failure of the current Ritz pairs
• the preconditioned correction block — \(W_k=T_kR_k\), shaped by a problem-aware approximate inverse or correction operator
• the compressed prior directions — \(P_k\), retaining useful search history without keeping a globally growing basis
• the local trial subspace — \(\mathcal S_k=\operatorname{span}\{X_k,W_k,P_k\}\), with the prior block empty at initialization
• the Rayleigh–Ritz extraction — the small projected generalized eigensolve that selects the next block and updates prior directions
• the metric and constraint discipline — \(B\)-orthogonality among active, constrained, and locked subspaces, with numerical rank monitored
• the convergence contract — scaled residual tests, iteration safeguards, and a terminal distinction among convergence, locking, restart, and failure

The signature is conjunctive. A block eigensolver without residual preconditioning is not the full identity. A preconditioned Davidson expansion without a fixed-width prior-direction recurrence is a sibling. Ordinary PCG with block right-hand sides lacks unknown Ritz values and a projected eigenproblem. Removing the Hermitian-definite contract changes which inner product, min-max principle, and extraction are valid.

The signature also separates mathematical identity from implementation choices. Constraints, hard or soft locking, restart thresholds, mixed precision, and particular orthogonalizers can vary while preserving the core. They become identity-changing when they remove the \([X,W,P]\) locally optimal recurrence or abandon the Hermitian-definite extreme-eigenpair problem.

What It Is Not

• Not ordinary conjugate gradient or PCG. Those methods solve a linear system with a known right-hand side. LOBPCG discovers eigenvalues along with eigenvectors and corrects \(AX-BX\Theta\), not \(b-Ax\).^[3]
• Not block CG. Block CG commonly solves several linear systems or uses a block Krylov space for a linear-system target. Its block residual and projected equations are not LOBPCG's block Ritz extraction.^[4]
• Not Lanczos with a longer name. Lanczos builds a Krylov recurrence and a tridiagonal projection. Even when unpreconditioned single-vector iterates lie in a related Krylov space, the approximants and stored subspace contract differ.
• Not Davidson or generalized Davidson. Davidson-type methods also use preconditioned residuals, but normally expand a growing or restarted subspace. LOBPCG compresses history into the fixed-width \([X,W,P]\) recurrence.
• Not Jacobi–Davidson. Jacobi–Davidson constructs a direction through a projected correction equation, often using an inner solve. LOBPCG directly preconditions the eigen-residual and locally extracts from a short block subspace.^[5]
• Not Rayleigh–Ritz itself. Rayleigh–Ritz is the local extraction engine. It does not supply the outer recurrence, residual preconditioner, block history, stability policy, or convergence loop.
• Not a generic eigensolver. The canonical identity is for a few extreme eigenpairs of a Hermitian-definite problem. Nonsymmetric pencils, arbitrary interior targets, and full dense decompositions require other contracts.
• Not globally optimal over all history. “Locally optimal” refers to the present trial space, not the best possible subspace of that dimension and not a global optimization that retains every former residual.
• Not universally accelerated by any preconditioner. A poor, incompatible, or unstable preconditioner can waste work or damage convergence. Classical guarantees have hypotheses.
• Not storage-free because it is matrix-free. The method stores several \(n\times m\) blocks and pays for orthogonalization, operator actions, and a dense projected eigensolve.
• Not automatically accurate when Ritz values stop changing. Residual norms, backward error, eigenvalue error, and invariant-subspace angle are different quantities, especially near clusters.

Scope of Application

LOBPCG travels literally wherever a large Hermitian-definite partial eigenproblem admits efficient block operator actions and a useful residual preconditioner. These are technical habitats inside numerical linear algebra and computational science, not metaphors.

• Sparse PDE eigenproblems. Finite-element stiffness–mass pencils and finite-difference Laplacians ask for a few low vibration, diffusion, or wave modes. Multigrid and domain-decomposition components developed for linear systems can often be adapted as eigen-residual preconditioners.^[6]
• Electronic-structure calculations. Large Hermitian Hamiltonians require blocks of low-energy states. Block operator products and warm starts across related self-consistent iterations make short-recurrence eigensolvers attractive; basis stability becomes crucial when many bands are requested.
• Mechanics and vibration. Generalized problems \(Kx=\lambda Mx\) use a symmetric stiffness matrix and positive-definite mass matrix. The desired lowest modes naturally fit the min-max and \(B\)-orthogonality contract.
• Graph and data spectra. Symmetric graph Laplacians, covariance operators, and singular-value reductions can expose a few extremal invariant directions without a full decomposition, provided the transformed problem remains Hermitian-definite.
• Parallel scientific computing. Block matrix–matrix actions exploit dense kernels and amortize communication, while PETSc/hypre and SLEPc integrations connect LOBPCG to scalable preconditioners and distributed vector spaces.^[6][7]
• Warm-started parameter sequences. Nearby meshes, parameter values, or outer nonlinear iterations can supply an initial \(X_0\) close to the next invariant subspace. LOBPCG accepts the whole block as state rather than discarding this information.
• Constrained eigenproblems. An implementation may require the active block to remain \(B\)-orthogonal to a supplied constraint space, as in removing a known null mode. The constraint is an explicit extension, not an invisible default.^[8]

The scope narrows when the requested block is not small relative to \(n\). Each full iteration may solve a dense projected eigenproblem of order up to about \(3m\), so orthogonalization and cubic projected work eventually dominate. SciPy's implementation explicitly recommends a large ratio of ambient dimension to requested block size and falls back to a dense solver when that ratio is too small.^[8]

Interior eigenvalues also mark a boundary. Shift-and-invert, harmonic extraction, filtering, or extended locally optimal methods can move the target, but those additions change operator cost, definiteness, and stability assumptions. They should be named rather than silently absorbed into the base node.

Clarity

The method becomes clearer when its four adjectives are read as a recognition test rather than promotional language. Local identifies the current short trial space. Optimal identifies a Rayleigh–Ritz min-max choice inside that space. Block identifies simultaneous invariant-subspace approximation. Preconditioned conjugate gradient identifies residual shaping plus retained prior directions. If any of those roles is missing, the method has moved to a neighbor.

Three matrices named in the formula also play different roles. \(A\) is the Hermitian operator whose spectrum is sought. \(B\) defines the generalized metric and must be positive definite in the canonical contract. \(T_k\) is a preconditioner applied to residuals; it is not the right-hand-side matrix and need not equal \(A^{-1}\). In a standard problem \(B=I\), but that does not make the preconditioner the identity.

The residual is an eigen-residual, not a linear-system residual with known \(\lambda\). Each column

\[ r_j=Ax_j-\theta_jBx_j \]

depends on the current Ritz value \(\theta_j\), which changes with the subspace. This is why ordinary PCG cannot simply be invoked: treating a Ritz value as already exact would replace the nonlinear eigenpair search by a different homogeneous linear problem.

“Matrix-free” should likewise be read operationally. An application may pass callables or linear-operator objects for \(A\), \(B\), and \(T\); the solver still applies them to whole blocks and forms Gram/projected matrices such as \(S^*AS\) and \(S^*BS\). The representation can be implicit while the linear algebra remains literal.

Finally, convergence and stopping are separate. In exact arithmetic the current subspace is contained in the next local trial subspace before extraction, which supports monotonic Ritz-value behavior for a consistently selected spectral end. Finite precision, rank loss, restarts, approximate preconditioning, and relabeling inside clusters complicate that slogan. A production result should report a residual-based or backward-error test and the terminal reason, not only a nearly stationary eigenvalue.

Manages Complexity

LOBPCG replaces a full eigendecomposition of a large operator with repeated work on a narrow block. The expensive ambient actions—\(AX\), \(BX\), and \(TR\)—can be executed as sparse or matrix-free block operations. Global spectral selection is compressed into a dense projected problem whose order depends on \(m\), not \(n\). This is the central scale separation: large physics in the operator actions, small exact algebra in Rayleigh–Ritz.

The prior-direction block manages history. A globally expanding Krylov or Davidson space can accumulate rich information but requires growing storage, orthogonalization, and eventually restart. LOBPCG retains only a compressed direction block \(P_k\), seeking much of the acceleration of history without keeping all of it. Local optimality chooses the best combination available in that restricted memory.

Blocking manages spectral clusters. A single vector can converge slowly or arbitrarily select a direction when several eigenvalues are equal or close. A block can represent the desired invariant subspace and let Rayleigh–Ritz rotate its columns together. This does not abolish multiplicity problems: a block that is too small, rank-deficient, or poorly orthogonalized can still miss directions.

Preconditioning manages spectral spread by turning residual components into corrections that better approximate missing eigenvector components. The same move creates a design dependency. One must choose, apply, and sometimes parallelize \(T\); stronger preconditioning can lower iteration count while raising per-iteration cost or communication. The right comparison is total time and attained accuracy, not iteration count alone.

Locking manages heterogeneous convergence within a block. When one Ritz pair meets tolerance earlier, removing it from active updates saves operator work. But the active block must remain orthogonal to the locked subspace or it can recreate the same mode. Soft locking may preserve it in extraction while skipping some updates; hard locking removes it and imposes a constraint. The policy belongs in the convergence contract.

Finite precision creates the last complexity layer. Near convergence, \(R_k\) is small and naive use of \(X_{k-1}\) beside \(X_k\) creates an ill-conditioned basis. Robust implementations form a numerically independent \(P_k\), orthogonalize blocks in the \(B\)-metric, detect rank loss, and use a backward-stable stopping criterion.^[2] These operations do not decorate the method; they preserve the subspace that the exact recurrence assumes.

Abstract Reasoning

Recognition diagnostic. Look for the five-step closure: current block \(X\) → Ritz values → eigen-residuals \(R\) → preconditioned corrections \(W\) → Rayleigh–Ritz on \([X,W,P]\). If the update instead solves a correction equation, grows an unrestricted basis, or attacks \(Ax=b\), route to a neighbor.

Residual diagnosis. Column \(j\) is exact exactly when \(r_j=Ax_j-\theta_jBx_j=0\). A large residual says the current pair violates the eigen-equation, but its norm should be scaled against operator and Ritz quantities before comparing differently sized problems.

Preconditioner prediction. If \(T\) approximates the inverse action needed to correct slowly converging residual components, \(W=TR\) enriches the trial subspace in useful directions. If \(T\) maps residuals mostly back into the current space or amplifies numerical noise, local optimization cannot manufacture absent directions.

Block-size prediction. Increasing \(m\) can capture clusters, exploit block kernels, and improve separation from the unwanted spectrum. It also raises storage, orthogonalization, communication, and the projected eigensolve cost. The best block is large enough to contain the desired invariant subspace with margin, not automatically as large as memory permits.

Warm-start intervention. When solving a nearby problem, map the prior eigenvectors into the new discretization and use them as \(X_0\). A good initial subspace can reduce residuals and iterations; it must still be checked for rank and \(B\)-orthogonality.

Cluster diagnosis. Near-equal Ritz values make individual eigenvectors ill-conditioned even when the invariant subspace is accurate. Inspect the block residual and subspace, not just column-by-column identity. Rotations within an exact multiple eigenspace are not errors.

Basis-stability intervention. If the projected Gram matrix loses conditioning, reorthogonalize, drop dependent directions, or restart under a declared policy. Continuing to solve an ill-conditioned projected pencil can produce convincing but meaningless Ritz values.

Method-selection prediction. LOBPCG is compelling when a few extreme eigenpairs, useful preconditioning, and large \(n/m\) align. Lanczos or Krylov–Schur may win when preconditioning is unavailable; Davidson or Jacobi–Davidson may suit other correction structures or interior targets; a dense solver wins when most of the spectrum is wanted.^[9]

Knowledge Transfer

Within numerical linear algebra, LOBPCG transfers as an instrument. A finite-element vibration pencil, graph Laplacian, Hamiltonian, or covariance operator can reuse the same literal roles: a Hermitian-definite problem, current Ritz block, residuals, preconditioner, prior directions, local Rayleigh–Ritz extraction, and residual stopping. The operator implementation changes; the method does not.

The most useful transfer is from linear-system infrastructure to the eigenproblem without confusing the two algorithms. A multigrid or domain-decomposition component can be reused as \(T\) acting on eigen-residuals. BLOPEX was designed precisely to connect LOBPCG with hypre and PETSc preconditioners.^[6] What transfers is the approximate inverse action; the outer PCG linear-system recurrence does not.

The block design also transfers between hardware regimes. On a shared-memory machine it exposes matrix–matrix kernels; on a distributed mesh it amortizes operator communication across multiple vectors. Yet the same block increases global reductions for Gram matrices and Rayleigh–Ritz. Hardware changes the cost model, not the recognition test.

Beyond computational eigenproblems, the portable residue belongs to broader parents. prime:iteration owns repeated state refinement under a stopping rule. prime:optimization owns selecting the best feasible point under an objective, though here it is only an internal engine. A team process that keeps current proposals, new corrections, and prior directions may resemble \([X,W,P]\), but without a Hermitian eigenproblem, eigen-residual preconditioning, and Rayleigh–Ritz projection it is analogy, not LOBPCG.

The transfer rule is therefore strict: carry LOBPCG literally only where the generalized eigen-equation and its numerical operations remain well typed. Carry the parent Iteration or Optimization pattern elsewhere.

Examples

Canonical

Let

\[ A=\operatorname{diag}(1,4,9,16),\qquad B=I, \]

and ask for the two smallest eigenpairs. Start with the orthonormal block

\[ X_0=\begin{bmatrix}u_1&u_2\end{bmatrix},\qquad u_1=\frac{e_1+e_3}{\sqrt2},\quad u_2=\frac{e_2+e_4}{\sqrt2}. \]

The projected matrix is diagonal because the two columns have disjoint support:

\[ \Theta_0=X_0^*AX_0=\operatorname{diag}(5,10). \]

With identity preconditioning, \(W_0=R_0=AX_0-X_0\Theta_0\), so

\[ r_1=\frac{-4e_1+4e_3}{\sqrt2},\qquad r_2=\frac{-6e_2+6e_4}{\sqrt2}. \]

At initialization \(P_0\) is empty. The pair \((u_1,r_1)\) spans \(\{e_1,e_3\}\), and \((u_2,r_2)\) spans \(\{e_2,e_4\}\). Hence \(\operatorname{span}\{X_0,W_0\}=\mathbb R^4\). Rayleigh–Ritz extraction on this local space selects the two smallest exact pairs \((1,e_1)\) and \((4,e_2)\); their new residuals are zero. This constructed one-step result demonstrates the subspace logic, not a universal convergence rate.

Mapped back: \((A,I)\) is the Hermitian-definite eigenproblem; the two smallest eigenvalues are the extreme spectral target; \(X_0\) is the current Ritz block; \((5,10)\) is the block Rayleigh readout; the two displayed vectors form the eigen-residual block and, because \(T=I\), the preconditioned correction block; \(P_0=\varnothing\) is the compressed-prior initialization boundary; \([X_0,W_0]\) is the local trial subspace; selecting \(e_1,e_2\) is the Rayleigh–Ritz extraction; orthonormality supplies the metric discipline; zero terminal residuals supply the convergence contract.

Applied / In Practice

The BLOPEX implementation study applied LOBPCG to the standard seven-point finite-difference discretization of the three-dimensional Laplacian on problems ranging from \(10^5\) to \(10^8\) unknowns, using PETSc domain-decomposition and hypre multigrid preconditioning on distributed and shared-memory systems.^[6] The target was a block of low-order modes of a large sparse symmetric problem.

In that setting, \(AX_k\) is obtained by applying the seven-point stencil to each current vector rather than by dense factorization. The block residuals measure how far the approximate modes fail \(AX=X\Theta\). A multigrid or domain-decomposition action turns them into \(W_k\), while \(P_k\) carries compressed previous progress. Rayleigh–Ritz on \([X_k,W_k,P_k]\) couples the candidate modes, rotates them through clustered spectral directions, and returns the next block. Distributed block operations amortize operator work, but global inner products and the projected eigensolve remain synchronization points. Converged low modes may be locked only while the active block remains orthogonal to them.

Mapped back: the Laplacian is the Hermitian-definite problem; its low modes are the extreme target; distributed approximate modes are the current Ritz block; projected eigenvalues are the Rayleigh readout; stencil defects are the residuals; hypre/PETSc components supply the preconditioned corrections; \(P_k\) is the compressed history; the three-block basis is the local trial space; its dense solve is the extraction; distributed orthogonalization and locking are the metric discipline; scaled residual norms and terminal status are the convergence contract.

Structural Tensions

T1: Local optimality versus global memory. Restricting extraction to \([X,W,P]\) keeps memory and projected work bounded, while a globally growing space may contain directions the short recurrence has discarded. Local optimality is exact on the retained subspace but cannot optimize over information it no longer has. Diagnostic: does bounded memory outweigh the convergence benefit of retaining or restarting a larger subspace?

T2: Block robustness versus block overhead. A wider block captures clusters and exploits matrix–matrix kernels, yet increases storage, global inner products, orthogonalization, and a projected eigensolve whose order is up to roughly \(3m\). Diagnostic: is the block large enough to span the desired cluster with margin but still small relative to the ambient problem?

T3: Strong preconditioning versus total cost. A better preconditioner may cut outer iterations, but construction, application, memory, or communication can dominate. An incompatible preconditioner can also erode theory or stability. Diagnostic: compare total time and attained residual/backward error under the preconditioner's actual hypotheses, not outer iterations alone.

T4: Matrix-free storage versus hidden operator cost. Avoiding explicit matrix assembly can make enormous problems possible, but an implicit operator may be expensive, communication-heavy, or difficult to precondition. The matrix disappears from storage, not from computation. Diagnostic: which cost dominates each block action—arithmetic, memory traffic, communication, or preconditioner setup?

T5: Short recurrence versus basis conditioning. Successive Ritz blocks and shrinking residuals make a naive \([X_k,R_k,X_{k-1}]\) basis nearly dependent precisely when high accuracy is sought. Stable basis selection adds orthogonalization and rank decisions that the ideal recurrence hides. Diagnostic: is the projected \(B\)-Gram matrix well conditioned, and is rank loss handled before Rayleigh–Ritz?

T6: Locking efficiency versus duplicate modes. Removing converged vectors saves block actions, but active vectors can drift back toward those modes if orthogonality constraints are not maintained. Keeping locked vectors in every extraction costs more. Diagnostic: is locking hard or soft, and how is the active block kept \(B\)-orthogonal to the locked subspace?

T7: Cheap stopping versus trustworthy accuracy. Ritz-value stagnation and raw residual norms are easy to monitor; backward-stable or scaled criteria are more reliable but demand operator-aware normalization and careful reporting. Clustered eigenvectors can remain individually uncertain even when their subspace is accurate. Diagnostic: what exactly is bounded at termination—raw residual, scaled backward error, eigenvalue error, or invariant-subspace angle?

T8: Autonomy versus reduction. LOBPCG is Iteration acting on an Eigenvalue/Eigenvector problem and internally using Optimization, yet those parents do not force the block preconditioned residual, prior-direction compression, and local Rayleigh–Ritz closure. Diagnostic: if the Hermitian pencil and \([X,W,P]\) recurrence remain jointly necessary, preserve LOBPCG; if they disappear, route the claim to Iteration, Optimization, or a generic eigensolver.

Structural–Framed Character

LOBPCG is structural-leaning on the structural–framed spectrum. Its eigen-equations, residuals, trial subspaces, and Ritz extraction are formal relations with no intrinsic praise or blame. A converged small eigenvalue is not “good” until an application supplies a goal.

On evaluative weight, it is structural: the method states a computational contract and diagnostic conditions. On human-practice-bound, it leans structural in the mathematical sense—the equations remain true without an institution—yet the algorithm, stopping rules, and finite-precision basis choices are designed practices rather than observer-free natural processes. On institutional origin, it leans framed because LOBPCG is an artifact of numerical linear algebra, published with a named recurrence and maintained in scientific software. On vocabulary travels, it remains domain-bound: Ritz block, Hermitian-definite pencil, preconditioned eigen-residual, \(B\)-orthogonality, and Rayleigh–Ritz retain literal meaning only in spectral computation. On import versus recognize, practitioners recognize the same method across PDEs, mechanics, graph spectra, and electronic structure; outside computational eigenproblems, uses are imported analogies.

The portable skeleton is prime:iteration: a state is repeatedly transformed using current error information and retained progress until a stop condition. Optimization also appears internally, but local Rayleigh–Ritz selection is not the whole named method. The cross-domain reach belongs to those broader patterns, while the full LOBPCG vocabulary stays in numerical eigensolving.

Its character: a formally neutral, highly structural numerical instrument whose exact recurrence travels widely inside computational science but whose identity dissolves when the Hermitian eigenproblem and Ritz machinery are removed.

Structural Core vs. Domain Accent

This section decides why LOBPCG is a domain-specific abstraction and not a prime.

What is skeletal (could lift toward a cross-domain prime). The thinnest portable pattern is iterative correction with bounded memory: carry a current state, diagnose its defect, transform the defect into a correction, combine the correction with compressed prior progress, choose the best available next state, and stop under a declared test. prime:iteration owns that repeated state-refinement skeleton. A second, subordinate skeleton is constrained local optimization: select the best candidate inside a deliberately limited search space. Neither skeleton is proprietary to LOBPCG.

What is domain-bound. Everything that makes the method recognizably LOBPCG remains numerical-linear-algebraic: a Hermitian or symmetric pencil with \(B>0\); a block of Ritz vectors and values; the residual \(AX-BX\Theta\); a spectral preconditioner; \(B\)-orthogonality; a retained direction block; a projected eigenproblem on \([X,W,P]\); cluster-aware locking; and scaled eigen-residual stopping. Remove the generalized eigen-equation and “residual,” “block,” “preconditioner,” and “optimal” no longer refer to the same operations. Even the word conjugate gradient is domain-accented here: it signals an eigensolver recurrence related to, but not identical with, linear-system CG.

Why this does not clear the prime bar. A prime's role vocabulary survives substitution and its cross-domain transfer is recognition of the same mechanism. LOBPCG's full role package is recognized across mechanics, materials, PDEs, and data spectra because all instantiate the same Hermitian-definite partial eigenproblem. Replace those substrates with an organizational or biological process and the Ritz quotient, eigen-residual, \(B\)-metric, and projected pencil become metaphors. The useful general lesson is already carried by Iteration and, more weakly, Optimization. The named method earns an autonomous node because those parents do not entail its joint technical closure, but its cross-domain reach stops where the eigenproblem stops.

The node is not a mere composite. Iteration plus Eigenvalue/Eigenvector plus Matrix plus Optimization still leaves open Lanczos, Davidson, Jacobi–Davidson, subspace iteration, dense QR, and many other algorithms. Only LOBPCG jointly fixes block residual preconditioning, compressed prior directions, and locally optimal extraction on the three-block trial space.

Instantiates / Related Primes

• prime:iteration — proposed strict subsumption parent. LOBPCG carries a current block state, repeatedly applies one update closure, measures progress by residuals, and terminates under a stopping rule. The child adds the Hermitian-definite spectral target and \([X,W,P]\) recurrence.
• prime:eigenvalue_and_eigenvector — proposed strict presupposition. The generalized eigen-equation, Ritz values, invariant subspace, and eigen-residual are constitutive. LOBPCG computes eigenpairs but is not a subtype of an eigenpair.
• domain_specific:matrix — related representation, declined as a direct parent. Matrices may represent \(A\) and \(B\), but matrix-free operator actions are sufficient. The Eigenvalue/Eigenvector parent carries the more exact linear spectral object.
• prime:optimization — internal engine, not proposed parent. Rayleigh–Ritz makes each update locally optimal in its trial space, but generic Optimization neither entails nor identifies the eigensolver.
• prime:convergence — related success property. Convergence and rate determine suitability; a failed run still executed LOBPCG.
• prime:approximation — related output status. Ritz pairs are approximations before convergence, but this remote property adds no useful direct placement once Iteration and the eigenpair target are explicit.

No structured dag_edges are written in this isolated draft. The proposed two-parent placement remains a working claim for independent audit.

Relationships to Other Abstractions

Current abstraction Locally Optimal Block Preconditioned Conjugate Gradient Domain-specific

Parents (2) — more general patterns this builds on

• Locally Optimal Block Preconditioned Conjugate Gradient is a kind of Iteration Prime

  prime:iteration — proposed strict subsumption parent. LOBPCG carries a current block state, repeatedly applies one update closure, measures progress by residuals, and terminates under a stopping rule.

• Locally Optimal Block Preconditioned Conjugate Gradient presupposes Eigenvalue And Eigenvector Prime

  prime:eigenvalue_and_eigenvector — proposed strict presupposition. The generalized eigen-equation, Ritz values, invariant subspace, and eigen-residual are constitutive.

Hierarchy paths (3) — routes to 3 parentless roots

• Locally Optimal Block Preconditioned Conjugate Gradient → Iteration

Show alternative paths (2)

Neighborhood in Abstraction Space

Locally Optimal Block Preconditioned Conjugate Gradient sits in a sparse region of the domain-specific corpus (85^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (1565 abstractions)

Nearest neighbors

• Birman–Schwinger Principle — 0.83
• Fredholm Kernel — 0.81
• Jacobi Method — 0.80
• Daniell Integral — 0.80
• Matrix Difference Equation — 0.80

Computed from structural-signature embeddings · 2026-09-08

Not to Be Confused With

• Preconditioned conjugate gradient (PCG). PCG solves \(Ax=b\) using a linear-system residual and conjugate directions; LOBPCG solves an unknown eigenpair problem and recomputes Ritz values. Tell: is the target a known right-hand side or an invariant direction with an unknown scalar?
• Block conjugate gradient. Block CG advances several linear-system right- hand sides or a block Krylov solve. LOBPCG's columns approximate several eigenvectors and are mixed by a projected eigenproblem. Tell: does the small problem enforce block linear equations or extract Ritz pairs?
• Lanczos method. Lanczos builds a Krylov basis and tridiagonal projection, typically without direct preconditioning of every current eigen-residual. LOBPCG retains only \([X,W,P]\) and locally reoptimizes there. Tell: is the recurrence generating a Krylov/tridiagonal basis or a preconditioned three-block Ritz trial space?
• Davidson or generalized Davidson. Davidson expands a growing/restarted subspace with residual corrections; LOBPCG compresses old information into \(P\) and keeps a fixed-width local space. Tell: does the method retain an expanding basis or only current, correction, and prior-direction blocks?
• Jacobi–Davidson. Jacobi–Davidson uses a projected correction equation, often with an inner iterative solve. LOBPCG directly applies \(T\) to the residual. Tell: is a correction equation being solved or is the residual simply preconditioned before Rayleigh–Ritz?
• Rayleigh–Ritz method. Rayleigh–Ritz extracts approximate eigenpairs from any supplied subspace. LOBPCG is one outer scheme that constructs the subspace repeatedly. Tell: where do \(W\), \(P\), and the next trial subspace come from?
• Subspace iteration. Subspace iteration repeatedly applies an operator (possibly an inverse/filtered one) to a block and reorthogonalizes. It does not by itself impose LOBPCG's residual-preconditioned locally optimal three-term recurrence. Tell: is the next block an operator image or the Ritz optimum over \([X,W,P]\)?
• Generic eigensolver. Dense QR, Arnoldi, contour, and Krylov–Schur methods cover different problem classes and spectral regions. Tell: are the Hermitian-definite extreme target and the LOBPCG recurrence both present?
• BLOPEX. BLOPEX is a software package that implements LOBPCG through hypre and PETSc, not the mathematical method's alternate name. Tell: is the statement about the algorithmic recurrence or a particular library and interface?
• Single-vector LOBPCG. Block size one preserves the local three-term eigenvalue recurrence but cannot simultaneously represent a multi-vector invariant subspace. Tell: is “block” carrying multiple active Ritz vectors or only naming the general family?
• Interior-eigenvalue extensions. Shift-invert, harmonic, filtered, and extended locally optimal solvers alter extraction and operator assumptions. Tell: is the target a raw smallest/largest spectral end or an interior region reached through an explicit transformation?

References

[1] Andrew V. Knyazev, “Toward the Optimal Preconditioned Eigensolver: Locally Optimal Block Preconditioned Conjugate Gradient Method”, SIAM Journal on Scientific Computing 23(2), 2001, pp. 517–541. Originating LOBPCG paper; local optimization of a three-term block recurrence and primary solver comparisons. Verified 2026-08-26. registry ↩

[2] Jed A. Duersch, Meiyue Shao, Chao Yang, and Ming Gu, “A Robust and Efficient Implementation of LOBPCG”, SIAM Journal on Scientific Computing 40(5), 2018, pp. C655–C676. Trace formulation, basis selection, finite-precision stability, and backward-stable stopping. Verified 2026-08-26. registry ↩a ↩b

[3] Magnus R. Hestenes and Eduard Stiefel, “Methods of Conjugate Gradients for Solving Linear Systems”, Journal of Research of the National Bureau of Standards 49(6), 1952, pp. 409–436. Primary linear-system conjugate-gradient boundary. Verified 2026-08-26. registry ↩

[4] Dianne P. O'Leary, “The Block Conjugate Gradient Algorithm and Related Methods”, Linear Algebra and its Applications 29, 1980, pp. 293–322. Primary block-CG and multiple-right-hand-side boundary. Verified 2026-08-26. registry ↩

[5] Gerard L. G. Sleijpen and Henk A. van der Vorst, “A Jacobi–Davidson Iteration Method for Linear Eigenvalue Problems”, SIAM Journal on Matrix Analysis and Applications 17(2), 1996, pp. 401–425. Primary Jacobi–Davidson and correction-equation boundary. Verified 2026-08-26. registry ↩

[6] A. V. Knyazev, M. E. Argentati, I. Lashuk, and E. E. Ovtchinnikov, “Block Locally Optimal Preconditioned Eigenvalue Xolvers (BLOPEX) in hypre and PETSc”, SIAM Journal on Scientific Computing 29(5), 2007, pp. 2224–2239. Parallel implementation, multigrid/domain-decomposition preconditioning, and 3-D Laplacian experiments at \(10^5\)–\(10^8\) scale. Verified 2026-08-26. registry ↩a ↩b ↩c ↩d

[7] SLEPc, “EPS: Eigenvalue Problem Solver”. Official solver taxonomy and Hermitian/generalized-Hermitian spectral-target support table. Verified 2026-08-26. registry ↩

[8] SciPy, scipy.sparse.linalg.lobpcg. Official API and implementation notes for operator inputs, generalized metric, constraints, residual histories, projected-problem size, and the large-\(n/m\) regime. Verified 2026-08-26. registry ↩a ↩b

[9] Yousef Saad, Numerical Methods for Large Eigenvalue Problems, revised edition, SIAM, 2011. Authoritative treatment of Lanczos, Krylov, subspace, Davidson, and partial eigenvalue methods. Verified 2026-08-26. registry ↩