Source-linked AI summary
A Density Matrix-based Algorithm for Solving Eigenvalue Problems
Eric Polizzi
TL;DR
Large-scale eigenvalue problems in electronic structure calculations remain computationally challenging. The paper introduces FEAST, a contour-integration and density-matrix-based algorithm, and reports efficiency, robustness, accuracy, and scalability, including relative residuals at or below 10−10 for up to 1000 eigenpairs.
Problem
Large-scale electronic structure calculations make diagonalization computationally challenging, especially when many atoms or eigenpairs are involved.
Method
FEAST uses an exact factorization of contour-integrated Green’s functions inspired by density matrix representation, followed by reduced generalized eigenvalue solution.
Results
Relative residuals equal to or smaller than 10−10 were consistently obtained when seeking up to 1000 eigenpairs, using M0 ≥ 1.5M, Ne = 8, and at most two refinement loops.
Takeaways & Limitations
FEAST provides a fundamentally different eigenvalue-solving approach that captures multiplicities without orthogonalization and supports basis reuse for refinement.
Abstract
from arXiv · showhide
A new numerical algorithm for solving the symmetric eigenvalue problem is presented. The technique deviates fundamentally from the traditional Krylov subspace iteration based techniques (Arnoldi and Lanczos algorithms) or other Davidson-Jacobi techniques, and takes its inspiration from the contour integration and density matrix representation in quantum mechanics. It will be shown that this new algorithm - named FEAST - exhibits high efficiency, robustness, accuracy and scalability on parallel architectures. Examples from electronic structure calculations of Carbon nanotubes (CNT) are presented, and numerical performances and capabilities are discussed.
I. INTRODUCTION
The paper frames large-scale eigenvalue computation as a central and increasingly difficult numerical challenge, then introduces FEAST as a fundamentally different robust and scalable approach.
- Generalized eigenvalue problems arise across science and engineering and require determining nontrivial solutions of Ax = λBx.
- Electronic structure calculations make diagonalization especially challenging when simulations contain more than one hundred atoms or require many eigenpairs.
- Traditional methods include Jacobi and power iterations, Krylov techniques such as Arnoldi and Lanczos, and Davidson-Jacobi approaches.
- The article presents FEAST as a new robust and scalable algorithm for solving eigenvalue problems.
- FEAST departs fundamentally from traditional techniques by drawing on density matrix representation and contour integration in quantum mechanics.
II. THE CONTOUR INTEGRATION TECHNIQUE IN ELECTRONIC STRUCTURE CALCULATIONS
Contour integration offers an alternative route to electron-density computation by integrating Green’s-function matrix elements, with a number of evaluations that can be independent of system size.
- Contour integration computes electron density from diagonal elements of the Green’s function G(Z) = (ZS − H)^−1 over complex energy space.
- At zero temperature, the contour includes eigenvalues below the Fermi level, while nonzero temperatures add Fermi-Dirac pole contributions on the imaginary axis.
- For transport and open systems, contour integration computes the equilibrium electron-density component while incorporating self-energy boundary conditions into H.
- Gauss quadrature typically requires approximately O(10) Green’s functions, independently of system size, making the approach attractive for electron-density calculations.
A. Introduction
FEAST solves generalized eigenvalue problems by exactly factoring a contour-integrated Green’s function into a subspace associated with eigenvectors inside the contour, then applying Rayleigh-Ritz reduction.
- The method targets Ax = λBx with A real symmetric or Hermitian and B symmetric positive definite over a specified eigenvalue interval.
- Rather than decomposing the Green’s function directly, FEAST exactly factors its contour integration, which represents the reduced density matrix.
- The factorization is expressed through eigenvectors inside the contour, whose outer-product matrix corresponds to the density matrix representation.
- Multiplying the density matrix by linearly independent random vectors produces independent subspace vectors Q through contour linear-system solves.
- Rayleigh-Ritz reduces the original problem to a generalized eigenvalue problem of size M, yielding Ritz values λm = ϵm and eigenvectors X = QΦ.
- The resulting eigenvectors are naturally B-orthonormal.
B. Practical Considerations and Pseudocode
FEAST computes contour-integral subspace vectors numerically on a positive half-circle, then improves accuracy through refinement and oversampling choices. Its practical performance depends on balancing quadrature points, subspace size, and refinement loops.
- Contour integration: FEAST computes Q by numerically integrating G(Z)Y along a circular contour using Gauss-Legendre quadrature at selected contour points.The contour can be reduced to its positive half-circle because conjugate symmetry relates G(¯Z) and G(Z).
- Contour integration: For real symmetric problems, the contour formula uses the real part, while the Hermitian case uses the imaginary part of the integrated resolvent products.The corresponding vectors Y and Q are real for the real-symmetric formulation and complex for the Hermitian formulation.
- Accuracy refinement: Outer refinement reuses Y = BX after computing eigenvectors, causing Q to converge toward X because X^TBX = I.The trace of the eigenvalues provides a fast convergence test.
- Accuracy refinement: Using M0 > M random vectors enlarges the reduced problem and can improve robustness, but BQ must remain symmetric positive definite.The upper limit on M0 can be obtained a posteriori because Q vectors are not orthogonalized.
- Practical settings: With M0 ≥ 1.5M, Ne = 8, and at most two refinement loops, FEAST consistently achieved relative residuals of 10^-10 or smaller for up to 1000 eigenpairs.The sequential pseudocode targets all M eigenpairs inside a specified interval for generalized problems Ax = λBx.
IV. NUMERICAL EXPERIMENTS
The numerical experiments evaluate FEAST’s stability, robustness, and scalability on three eigenvalue problems derived from electronic-structure calculations of carbon nanotubes.
- Experimental scope: Three carbon-nanotube examples derived from electronic-structure calculations are used to demonstrate FEAST’s numerical stability, robustness, and scalability.The experiments are presented as numerical demonstrations of the algorithm’s performance and capabilities.
A. Example I
Example I evaluates FEAST on the Test-CNT generalized eigenproblem, comparing solver behavior, refinement accuracy, and contour-point choices. The reported results support strong residual accuracy and scalability, while limiting quantitative solver comparisons.
- Problem setup: Test-CNT is a 2D FEM discretization of DFT/Kohn-Sham equations for a (13,0) carbon nanotube, with real-symmetric A, s.p.d. B, N = 12,450, and nnz = 86,808.The two matrices have identical sparsity patterns.
- Solver comparison: Table I compares ARPACK with shift-invert and FEAST for up to M = 800 lowest eigenpairs using PARDISO on an 8-core Intel Clovertown node.Both methods use M0 = 1.5M, while FEAST uses Ne = 8 contour points.
- Scope of comparison: The simulations are not intended as a quantitative solver comparison because hardware, sequential factorization, solver choices, contour points, and stopping criteria affect performance.The runs use one node, and FEAST’s linear systems are factorized and solved one after another.
- Refinement accuracy: Only two to three refinement loops were necessary to obtain the small relative residuals reported for the Test-CNT cases.The convergence criterion uses a relative trace error of 10^-13.
- Refinement accuracy: One refinement loop produced eigenvalue accuracy of approximately 10^-5 or below.This result concerns eigenvalue accuracy rather than the final eigenpair residual criterion.
- Scalability and robustness: FEAST retained very good scalability as the search interval increased while Ne remained fixed at 8, keeping the numerical operations per loop unchanged.The fixed quadrature requires eight linear systems per loop.
B. Example II
Example II tests FEAST's robustness in capturing eigenvalue multiplicities using artificially repeated carbon-nanotube systems, with performance results reported for increasing repetition factors and solver comparisons.
- Performance setup: Table III reports FEAST performance while seeking M = 100 eigenpairs for different values of Ne.Convergence is defined by an error on the trace equal to or smaller than 10^-13.
- Multiplicity test: Repeated block-diagonal TEST-CNT systems model bundles of k noninteracting carbon nanotubes, making each eigenvalue k times degenerate.The systems are constructed by repeating matrices A and B k times along the main diagonal.
- Solver comparison: Table IV compares simulation times and relative residuals from ARPACK and FEAST on k(N, M) TEST-CNT systems.The comparison covers systems reproducing the original system k times and targets the kM lowest eigenpairs.
C. Example III
Example III applies FEAST successively across k points in a metallic carbon-nanotube bandstructure calculation, reusing each computed subspace as the next initial guess and achieving rapid refinement convergence.
- Accuracy: The trace-error convergence criterion is 10^-8, while iterative inner linear systems use 10^-3 accuracy and final eigenpair residuals range from 10^-3 to 10^-5.These settings demonstrate the reported accuracy tradeoff between inner solves, trace convergence, and final residuals.
- Bandstructure workflow: 13 to 20 eigenvalues are found within the selected search interval across the different k points.The reported eigenvalues correspond to energies along the Γ-to-X path.
- Convergence: After the initial point at k = 0, FEAST converges within only one refinement loop for almost all other k points.The reused subspace provides the starting point for iterative refinement across nearby problems.
V. DISCUSSIONS
The discussion presents FEAST as a direct, contour-integration-based alternative whose main computational burden is solving multiple-right-hand-side linear systems, while subspace reuse supports refinement and related problem sequences.
- Algorithmic character: FEAST is cast as a direct technique based on an exact mathematical derivation, unlike iterative Krylov subspace methods.Its formulation naturally captures eigenvalue multiplicities without requiring Gram-Schmidt orthogonalization.
- Computational structure: FEAST primarily requires solving Ne linear systems along the contour with M0 right-hand sides and a reduced dense generalized eigenvalue problem of size M0.The reduced problem follows the contour-based subspace construction.
- Reuse and refinement: Subspace reuse enables outer iterative refinement and benefits sequences of nearby eigenvalue problems, such as bandstructure calculations.The previously computed basis can serve as a suitable initial guess for subsequent problems.
- Scope and limitation: FEAST shifts difficulty from the eigenvalue problem to linear systems with multiple right-hand sides, and its scalability depends mainly on the linear system solver.Direct solvers may be limited by memory requirements for large-scale applications, while iterative solvers are an alternative.