Block Locally Optimal Preconditioned Eigenvalue Xolvers (BLOPEX) in hypre and PETSc

1. Introduction.

• BLOPEX gives the community easy access to customizable code for a preconditioned eigensolver.The native hypre version directly uses hypre multigrid preconditioners.Source: §1 · pp. 1–2
• The current release contains only LOBPCG for symmetric eigenproblems Ax = λBx.The method has also been implemented in several other software packages and programming languages.Source: §1 · p. 2
• The paper details the LOBPCG algorithm, hard and soft locking, the abstract implementation, and parallel performance.The performance discussion covers distributed and shared-memory systems using domain-decomposition and multigrid preconditioning.Source: §1 · p. 2, §2 · p. 2

2.1.1. The problem and the assumptions.

• For Ax = λBx, the method seeks the m smallest eigenpairs with symmetric A and symmetric positive definite B; A itself need not be positive definite.A real shift of A by αB leaves the formulas invariant.Source: §2.1.1 · p. 2
• The convergence-rate theory assumes a linear, symmetric, positive definite preconditioner, which may vary between iterations if it meets those conditions each time.Using a preconditioner that violates these assumptions may slow convergence or cause breakdown and instability.Source: §2.1.1 · p. 2

2.1.2. Single-Vector LOBPCG.

• LOBPCG minimizes the Rayleigh quotient over a trial subspace containing the current vector, preconditioned residual, and previous-iterate direction.The recurrence using an implicit difference direction is mathematically equivalent in exact arithmetic and helps address ill-conditioned Gram matrices from near-duplicate iterates.Source: §2.1.2 · p. 3

2.1.3. The LOBPCG Basics.

• The block method computes m Ritz vectors from a 3m-dimensional trial subspace, and block size should balance spectral coverage against Rayleigh–Ritz cost.Including a full eigenvalue cluster can aid convergence; the best block size also depends on the problem, software, and hardware.Source: §2.1.3 · p. 4

2.2. The Detailed Description of the LOBPCG Algorithm.

• Each iteration applies the preconditioner and the A and B matrix-vector products once per block, storing 9m vectors, or 6m when B = I.A lower-memory variant stores 3m vectors but requires extra matrix-vector products and is not available in BLOPEX.Source: §2.2 · p. 6
• BLOPEX B-orthonormalizes the residual and search-direction blocks with Cholesky-based Gram matrices, a cheaper but round-off-sensitive choice.The implementation prioritizes performance while aiming for reasonable reliability and accuracy typical of large-scale engineering applications.Source: §2.2 · p. 6

2.3. LOBPCG deflation by hard and soft locking.

• Soft locking removes converged vectors’ residuals from iteration but retains the vectors in Rayleigh–Ritz, allowing their accuracy to improve without tying active-vector accuracy to them.It costs more than hard locking; BLOPEX also uses hard locking through constraints.Source: §2.3 · pp. 7–8
• At residual tolerance 10^-1 with m = 10, soft-locked eigenpairs still improve in accuracy while active eigenpairs continue converging.Soft locking is especially beneficial when the stopping tolerance is not very small.Source: Figure 2.1 · p. 8, §2.3 · p. 8

3. Abstract BLOPEX implementation for PETSc and hypre.

• The abstract LOBPCG code uses user-supplied functions for matrix-vector products and preconditioning, while environment-specific interfaces provide parallel multivector operations.Figure 3.1 diagrams the BLOPEX modules for hypre and PETSc.Source: §3 · p. 9, Figure 3.1 · p. 9
• BLOPEX represents vector blocks such as X and P with an abstract “multivector” object whose implementation lies outside the code.PETSc and hypre interfaces currently reference individual vectors; true block multivectors are expected to reduce communication and improve BLAS use when available.Source: §3 · p. 9
• The reported tests use double-precision real arithmetic, and some may use different tolerances despite efforts to maintain consistency.Source: §3 · p. 9

4.1. The Basic Accuracy of Algorithm.

• Maximum relative error stayed below 10^-8 for both Laplacians, including one with multiple eigenvalues and one with distinct clustered eigenvalues.The tests computed the smallest 50 eigenvalues using BoomerAMG preconditioning and random initial approximations.Source: §4.1 · p. 9

4.2. Performance Versus the Number of Inner Iterations.

• For block-size m=1, Schwarz-PCG worked best with about 10–15 inner iterations, while BoomerAMG worked best applied directly.For the 100 × 100 × 100 Laplacian, the tests varied preconditioner quality by changing the maximum number of PCG inner iterations.Source: §4.2 · p. 10
• With block-size m=10, direct BoomerAMG was fastest and converged in 31 iterations; without preconditioning, 500 iterations took ten times longer and missed tolerance 10^-10.Source: §4.2 · p. 10

4.3. LOBPCG Performance vs.

• CPU time grew approximately linearly with block size through m=16; beyond that, m^2n complexity and slower convergence for larger eigenvalues affected timing.Figure 4.1 compares LOBPCG performance by block size using hypre BoomerAMG.Source: §4.3 · p. 11, Figure 4.1 · p. 11

4.4. Scalability.

• An eightfold increase in dual-CPU nodes did not noticeably raise CPU time; on Beowulf, 32-fold growth only slightly increased it.The Beowulf scalability figure uses 1M unknowns per node.Source: §4.4 · p. 11, Figure 4.2 · p. 11
• BlueGene/L tests used SMG geometric multigrid at tolerance 10^-6 and reported typical averages, with 10–20% variability in iteration counts and wall-clock time.The tests covered large matrix sizes and varied block sizes.Source: §4.4 · p. 12

4. BLOPEX LOBPCG Numerical Results in PETSc and hypre.

• BLOPEX was integrated into hypre and made available in PETSc as an external package; the paper tested its scalability on large model problems in parallel systems.Source: Conclusions · p. 12

• X stores the iterative eigenvector approximations, while A and B apply the first and second eigenproblem matrices to multivectors.Source: Appendix A · p. 14
• T applies the preconditioner, and Y supplies the constraint used for hard locking, with iterations restricted to its B-orthogonal complement.Source: Appendix A · p. 14
• W stores residuals and preconditioned residuals, P stores LOBPCG directions, and gramA and gramB are used in Rayleigh–Ritz.Source: Appendix A · pp. 14–15
• J indexes active iterates; converged indices leave J, while excluded indices correspond to soft-locked eigenvector approximations.Source: Appendix A · pp. 14–15
• R is the upper-triangular Cholesky factor used for B-orthogonalization, and C supplies coefficients for forming new Ritz vectors.Source: Appendix A · p. 15
• PETSc installation downloads and compiles BLOPEX and hypre through external-package configuration options, and includes a BLOPEX test driver.Source: Appendix B · p. 15
• hypre includes BLOPEX without special configuration; LOBPCG was tested with STRUCT, SSTRUCT, and IJ interfaces, but not FEM.Source: Appendix B · p. 15
• Testing used AMD workstations, SUN Fire 880, Beowulf and MCR clusters, and an IBM Blue Gene/L system.Source: Appendix C · pp. 15–16

• BLOPEX is a library for large-scale eigenvalue problems, available alongside PETSc and hypre software ecosystems.Source: §D.2 · p. 16
• PETSc supports scalable PDE computation, hypre provides scalable linear solvers, and SLEPc extends PETSc for large eigenvalue problems.Source: §D.2 · p. 16
• hypre’s interfaces include IJ for sparse matrices, STRUCT for logically rectangular grids, and SSTRUCT for mostly structured grids with some unstructured features.Source: §D.3 · p. 16
• PFMG is a parallel semicoarsening multigrid solver; its pointwise smoothing makes it less robust than SMG but more efficient per V-cycle.Source: §D.3 · p. 16

• PCG means Preconditioned Conjugate Gradient.Source: §D.4 · p. 16
• LOBPCG means Locally Optimal Block Preconditioned Conjugate Gradient.Source: §D.4 · p. 16
• AMG means algebraic multigrid.Source: §D.4 · p. 16