A greedy algorithm for computing eigenvalues of a symmetric matrix

Abstract

We present a greedy algorithm for computing selected eigenpairs of a large sparse matrix $H$ that can exploit localization features of the eigenvector. When the eigenvector to be computed is localized, meaning only a small number of its components have large magnitudes, the proposed algorithm identifies the location of these components in a greedy manner, and obtains approximations to the desired eigenpairs of $H$ by computing eigenpairs of a submatrix extracted from the corresponding rows and columns of $H$. Even when the eigenvector is not completely localized, the approximate eigenvectors obtained by the greedy algorithm can be used as good starting guesses to accelerate the convergence of an iterative eigensolver applied to $H$. We discuss a few possibilities for selecting important rows and columns of $H$ and techniques for constructing good initial guesses for an iterative eigensolver using the approximate eigenvectors returned from the greedy algorithm. We demonstrate the effectiveness of this approach with examples from nuclear quantum many-body calculations, many-body localization studies of quantum spin chains and road network analysis.

arXiv comment19 pages, 9 figures, 1 table

References in corpus (12)

• Many body localization and thermalization in quantum statistical mechanics
• Many-body localization edge in the random-field Heisenberg chain
• Heat-bath Configuration Interaction: An efficient selected CI algorithm inspired by heat-bath sampling
• Semistochastic Heat-bath Configuration Interaction method: selected configuration interaction with semistochastic perturbation theory
• A deterministic alternative to the full configuration interaction quantum Monte Carlo method
• Importance Truncation for Large-Scale Configuration Interaction Approaches
• Eigenvector localization in real networks and its implications for epidemic spreading
• Accelerating Nuclear Configuration Interaction Calculations through a Preconditioned Block Iterative Eigensolver
• Localization of eigenfunctions via an effective potential
• Coordinate descent full configuration interaction
• Principal eigenvector localization and centrality in networks: revisited
• Coordinate-wise descent methods for leading eigenvalue problem

Cited by in corpus (3)

• Optimal Orbital Selection for Full Configuration Interaction (OptOrbFCI): Pursuing the Basis Set Limit under a Budget
• Numerically Exact Configuration Interaction at Quadrillion-Determinant Scale
• Bootstrapped Block Lanczos for large-dimension eigenvalue problems