Decay properties of spectral projectors with applications to electronic structure

Michele Benzi; Paola Boito; Nader Razouk

Source-linked AI summary

Decay properties of spectral projectors with applications to electronic structure

Michele Benzi, Paola Boito, Nader Razouk

arXiv:1203.3953v1Mar 18, 2012math.NAcond-mat.mtrl-sciphysics.chem-phphysics.comp-ph

TL;DR

The paper studies decay properties of spectral projectors for large, sparse Hermitian matrices in electronic-structure settings where many-particle equations are nonseparable. It develops matrix-approximation and decay analyses that support linear-scaling methods, while examining temperature and spectral-gap effects and acknowledging conservative bounds.

Problem
Many-particle electronic-structure equations are nonseparable because of the electron–electron interaction term Vee, motivating analysis of spectral-projector decay for large sparse matrices.
Method
The paper uses graph-based matrix-decay analysis, approximation of rapidly decaying matrices by sparse or banded matrices, and basis transformations between non-orthogonal and orthogonal representations.
Results
The theory establishes decay bounds for density matrices whose behavior improves at higher electronic temperatures and captures the correct asymptotics for small gaps and low temperatures.
Takeaways & Limitations
The results provide a theoretical justification for O(n) electronic-structure methods and address both orthogonalization choices and sparse approximations relevant to implementation.
Takeaways & Limitations
The bounds are generally pessimistic, especially at zero or low temperatures, because polynomial-degree estimates ignore numerical cancellation and use worst-case sign patterns.

Abstract

from arXiv · show

Motivated by applications in quantum chemistry and solid state physics, we apply general results from approximation theory and matrix analysis to the study of the decay properties of spectral projectors associated with large and sparse Hermitian matrices. Our theory leads to a rigorous proof of the exponential off-diagonal decay ("nearsightedness") for the density matrix of gapped systems at zero electronic temperature in both orthogonal and non-orthogonal representations, thus providing a firm theoretical basis for the possibility of linear scaling methods in electronic structure calculations for non-metallic systems. We further discuss the case of density matrices for metallic systems at positive electronic temperature. A few other possible applications are also discussed.

1. Introduction.

The paper develops a rigorous mathematical foundation for linear-scaling electronic-structure methods by deriving decay bounds for density matrices in insulating and finite-temperature metallic systems. It uses approximation theory and matrix analysis to study locality in functions of sparse matrices, while emphasizing theory over specific algorithms.

Motivation: O(n) methods compute density matrices instead of diagonalizing Hamiltonians, reducing computational effort to linear scaling for many insulating systems.These methods target sufficiently large systems and encode important physical properties through the density matrix.
Motivation: Nearsightedness means that perturbation effects remain localized, producing rapid off-diagonal decay in the density matrix.The paper addresses the fact that this decay had often been assumed or established only in special cases.
Contributions: The paper derives decay bounds for general density matrices of insulators and metallic systems at positive electronic temperatures, including dependence on band gap and temperature.The treatment is mathematical and intended to provide a foundation for linear-scaling electronic-structure computations.
Contributions: The analysis combines classical approximation theory and matrix analysis with a general theory for analytic functions of sparse matrices.A functional-analytic model is used for a metallic regime where density-matrix decay is very slow.
Broader applications: The approach may also apply to large-matrix problems involving locality of interaction, including quantum statistical mechanics, information theory, complex networks, and numerical linear algebra.The discussion of these applications is brief and intended to stimulate further work.
Scope: The paper primarily studies the theory behind O(n) methods rather than specific computational algorithms.Algorithm-focused readers are directed to surveys of electronic-structure computation.

2. Background on electronic structure theories.

Electronic-structure theory begins with a many-electron problem whose electron–electron interaction prevents separation into independent one-electron equations. One-electron approaches, including density functional and Kohn–Sham methods, replace or approximate this problem through self-consistent single-particle calculations.

Many-electron problem: The many-particle Schrödinger equation cannot generally be separated into independent one-particle equations because of electron–electron repulsion.This non-separability motivates one-electron methods that reduce the number of unknowns per equation.
One-particle methods: For non-interacting particles, eigenstates can be represented by Slater determinants of occupied orbitals satisfying single-particle eigenvalue equations.Self-consistent one-particle methods retain this orbital-based structure while iteratively updating density-dependent terms.
Density functional theory: Density functional theory rewrites the ground-state energy as a functional of the electron density rather than the many-body wavefunction.The Hohenberg–Kohn result states that the potential is determined by the ground-state density up to a constant.
Kohn–Sham theory: The Kohn–Sham construction replaces the original non-separable system with fictitious non-interacting electrons having the same density.Its equations are solved self-consistently by updating the density and exchange-correlation potential until changes become negligible.
Approximations: Exchange-correlation energy is unknown in practice and is approximated through schemes such as LDA, LSDA, and GGA.These approximations respectively incorporate local-density, spin, and gradient information.
Computational simplifications: Pseudopotentials replace explicit core electrons by an effective nuclear attraction for valence electrons, especially in plane-wave calculations.This reduces the explicitly treated electronic degrees of freedom.

3. Density matrices.

The density matrix is formulated as a spectral projector onto occupied states, allowing electronic properties to be computed without explicitly diagonalizing the Hamiltonian. Its localization follows from sparse, localized representations and is central to linear-scaling approaches, with gap and temperature governing decay behavior.

Density matrices: The density matrix P is the S-orthogonal projector onto the Hamiltonian subspace spanned by the ne occupied eigenvectors.For an orthonormal basis, it is the spectral projector formed by summing occupied-state outer products.
Density matrices: Replacing Hamiltonian diagonalization with density-matrix computation works because physical quantities can be expressed as functionals of P.Self-consistent-field methods may require P repeatedly at increasing accuracy.
Sparsity and locality: Localized basis functions produce sparse or rapidly decaying Hamiltonian matrices, making banded and more general sparsity patterns relevant for decay analysis.The paper also develops graph-based notions for matrices whose decay follows more general sparsity structures.
Basis transformations: Non-orthogonal bases are transformed using inverse Cholesky or Löwdin factors, while the transformed Hamiltonian remains sparse up to truncation.The decay rate of the transformation factors depends on the conditioning of the overlap matrix.
Matrix functions: The zero-temperature projector is represented by a step function of H, while the analytic Fermi–Dirac function provides a tractable approximation when the spectral gap is not too small.Smaller gap γ requires larger β, interpreted as an inverse temperature, for accurate approximation.
Finite temperature: At positive electronic temperature, the Fermi–Dirac matrix function applies to metallic systems with small or vanishing gaps but is no longer an orthogonal projector.The same function supports calculation of thermodynamic and temperature-dependent quantities.
Decay bounds: Density-matrix localization for insulators has motivated linear-scaling algorithms, while the paper supplies universal but potentially conservative decay bounds.The bounds depend on Hamiltonian sparsity, spectral extremes, gap γ, and when relevant temperature, rather than a particular basis or discretization.

4. Related work.

Earlier work established important localization results but did not provide a fully general rigorous theory of density-matrix decay for localized Hamiltonians across gapped and finite-temperature metallic systems. This paper instead derives estimates directly for increasing finite matrices, targeting the matrix objects used in electronic-structure calculations.

Prior results: Prior literature includes rigorous model results, semi-rigorous system-specific estimates, and non-rigorous analyses based on heuristics, physical reasoning, and numerics.The paper distinguishes these levels of mathematical support when reviewing related work.
Prior results: Most previous localization results were formulated for continuous functions, density kernels, or Wannier functions rather than directly for finite matrices.The paper focuses on matrix decay because matrices are the primary computational objects in electronic-structure calculations.
Insulators: Kohn’s one-dimensional results and later Wannier-function work extended localization theory, while Chern-insulator cases left density-matrix decay questions open.The latter setting can prevent exponential Wannier-function decay.
Insulators: Known results include exponential decay estimates for broad classes of insulators and analyses of how decay rates depend on the spectral gap.Related studies also examined power-law factors and debated whether the decay rate scales with γ or √γ.
This paper’s approach: The paper establishes estimates directly for sequences of finite, increasing-order matrices under a minimal set of assumptions on discrete Hamiltonians.This approach is presented as closer to practical electronic-structure calculations than starting from a continuous problem and discretizing it.
Broader relevance: The increased generality is intended to support O(n) methods in other problems involving spectral projectors and related matrix functions.The paper points to additional applications beyond electronic structure.

5. Normalizations and scalings.

The paper assumes matrix sequences with bounded interaction ranges, uniformly bounded spectra, and a non-vanishing spectral gap, while noting important limitations for some discretizations and metallic systems.

The bandwidth of H_n remains bounded as system size increases, reflecting a fixed interaction range for discretized Hamiltonians.
The spectra of H_n are uniformly bounded as the number of electrons grows.
A uniform spectral gap, inf_n γ_n > 0, means the electronic-structure problem remains uniformly well-conditioned; metals violate this assumption.
These assumptions generally apply to localized basis representations, but not to non-localized bases such as plane waves.
For PDE discretizations, bounded bandwidth and a non-vanishing gap generally cannot both be maintained as the discretization is refined.
Localized orbital bases produce formally full Hamiltonian and overlap matrices because their basis functions are globally supported, despite rapid decay outside localized regions.

6. Approximation of matrices by numerical truncation.

The paper develops truncation results showing that matrices with distance-based decay can be approximated accurately by banded or sparse matrices, with approximation widths independent of system size.

Exponential off-diagonal decay is defined by |[A_n]_ij| ≤ c e^(-α|i-j|), with c and α independent of n.
The truncated matrix is the Frobenius-norm best approximation within the subspace of m-banded matrices.
For any tolerance ϵ, an exponentially decaying matrix can be approximated in norm by an m-banded matrix with sufficiently large m.
When decay constants are independent of n, the required bandwidth is also independent of n, including in the Hermitian 2-norm setting.
The same truncation framework covers algebraic decay with exponent p > 1, although its approximation widths can be less favorable than for exponential decay.
For bounded-degree graphs, retaining entries within graph distance m yields norm accuracy with m independent of n, while the approximant contains only O(n) nonzeros.
Localized basis functions make Hamiltonian and overlap matrices sparse, with linearly growing nonzero counts, though per-row density can still be high.

7. General properties of orthogonal projectors.

The paper establishes general sparsity and truncation properties for orthogonal projectors, then applies decay assumptions to density matrices and their electronic-structure objective functions.

The density-matrix energy functional is Tr(PH), and approximating P and H introduces separate projector, Hamiltonian, and cross-error terms.
For any fixed threshold ϵ, the number of entries of a density matrix with magnitude at least ϵ grows at most linearly with n.
Linear or algebraic decay with small exponent permits fixed-bandwidth approximation in Frobenius norm, but the resulting widths may be impractical.
Exponential decay gives the more favorable truncation-width scaling m = O(ln ϵ^-1), independent of system size.
With exponential decay on bounded-degree graphs, density matrices admit sparse approximations containing only O(n) nonzeros for any prescribed tolerance.
For large systems, the normalized energy error is essentially determined by Hamiltonian truncation error rather than density-matrix error.
The estimates give approximately equal weight to Hamiltonian and density-matrix errors when the basis-function-to-electron ratio is a moderate constant.
The paper analyzes decay for Fermi–Dirac functions and density matrices in banded and general sparse settings using polynomial approximation tools.

8. Decay results.

The paper derives decay bounds for Fermi–Dirac functions of sparse Hermitian matrices and applies them to density matrices, including zero-temperature spectral projectors for gapped systems. The bounds clarify how decay depends on spectral gaps, temperature, sparsity, and system size.

General decay bounds: Theorem 8.1 establishes exponential decay bounds for Fermi–Dirac functions of uniformly bounded, m-banded Hermitian matrices.The constants in the bound are independent of matrix size n.
Parameter dependence: Choosing χ involves a trade-off: larger χ improves asymptotic decay, whereas values near the nearest poles can make the prefactor c very large and the bound pessimistic.For the illustrated case, χ = 1.3 is more useful than χ = 1.362346 for estimating a truncation bandwidth.
Parameter dependence: Higher electronic temperature produces faster decay because smaller β improves the asymptotic behavior of the Fermi–Dirac bound.The bound’s parameter choice also involves the ellipse Eχ, uniquely characterized by χ.
General decay bounds: The decay bound extends to general sparsity patterns using graph distance, but linear-scaling implications require uniformly bounded graph degree.Under this restriction, graph distance grows with index separation and supports O(n) approximations.
Zero-temperature density matrices: For zero-temperature gapped systems, the density matrix is a spectral projector and inherits exponential off-diagonal decay from the approximation results.Corollary 8.6 gives an a priori bandwidth, independent of n, outside which projector entries are below a prescribed tolerance τ.
Zero-temperature density matrices: In the C52H106 example, the HOMO–LUMO gap is approximately 0.1, and the density-matrix bandwidth remains virtually unchanged as the alkane chain grows.This size independence underlies the feasibility of O(n) approximations for large systems.

8.3. Proof of decay bounds.

The section derives density-matrix decay bounds by combining polynomial approximation of analytic functions with sparsity-induced locality. It compares Bernstein-, Hasson-, and disjoint-interval-based bounds, including their practical conditions and limitations.

Bernstein bounds: Bernstein’s theorem bounds analytic-function approximation errors on ellipses Eχ, yielding matrix-entry decay through polynomial approximants.The bound depends on the ellipse parameter χ and M(χ), the maximum modulus of the function on Eχ.
Fermi–Dirac case: For the Fermi–Dirac function, smaller β places its poles farther from the real axis and produces faster decay bounds.The admissible ellipse is constrained by the nearest poles of f_FD(z).
Sparsity and distance: The resulting bounds extend from banded matrices to general sparsity patterns by relating polynomial degree to graph distance.Polynomial powers cannot connect entries whose graph distance exceeds the polynomial degree.
Uniformity: Under bounded maximum degree, the decay rate is independent of matrix size n.This establishes uniform asymptotic decay for growing sparse Hamiltonian sequences.
Limitations: The disjoint-interval bound requires symmetry of the spectral intervals and cannot be assessed practically without an explicit or estimated constant K.Its quality deteriorates when the chosen spectral endpoints poorly match the extreme eigenvalues.
Additional bounds: Disjoint-interval approximation generally gives a higher asymptotic decay rate and reduces the required truncation bandwidth by a factor of three in the tridiagonal case.The reduction is reported as independent of the spectral-gap size.

8.6. Dependence of the rate of decay on the spectral gap.

The section studies how decay bounds depend on the spectral gap when the Fermi level lies at the gap midpoint. For small gaps, the bound’s decay behavior is first-order proportional to the gap.

Setup: For midpoint Fermi levels, the section analyzes the asymptotic dependence of decay bounds on the absolute spectral gap γ.The analysis uses the equivalent interval parameter a under normalized spectral bounds.
Asymptotic dependence: For small γ, the decay behavior is described at first order by γ itself rather than a more complicated function of γ.The authors characterize this as a conservative general upper-bound estimate.
Relation to prior estimates: A square-root dependence reported for some systems remains consistent because, for upper bounds, it corresponds to faster decay at small gap values.The paper therefore does not claim that the alternatives contradict its bound.

8.7. Dependence of the rate of decay on the temperature.

The section resolves the low-temperature scaling of decay in metallic systems at positive temperature. Its approach shows that the decay length is proportional to kBT.

Temperature dependence: The decay length is proportional to T at low temperatures.The result follows from the behavior of the analytic Fermi–Dirac approximation parameters.
Conclusion: The paper concludes that the low-temperature decay length is proportional to kBT and presents this as a fully rigorous general result.The conclusion agrees with earlier results cited by the authors.

8.8. Other approaches.

The section derives projector decay bounds using a contour-integral representation and extends them to general sparsity patterns. It also notes computational usefulness and difficulties in evaluating the resulting constants.

Contour representation: A spectral projector can be represented by a contour integral around exactly the occupied eigenvalues of Hn.Componentwise decay follows by analyzing the resolvent along the contour.
Uniform bounds: For banded Hamiltonians with uniformly bounded spectra and bandwidths, resolvent estimates provide constants independent of n.Uniformly positive spectral gaps ensure the relevant constants remain finite.
Decay result: The contour method yields exponential decay bounds with positive constants C and α independent of n.The same form extends to general sparsity patterns.
Limitation: A disadvantage of the contour approach is that explicitly evaluating its decay constants C and α is rather complicated.The bounds are therefore less straightforward to use quantitatively despite their theoretical generality.
Computation: Quadrature of the contour integral produces a rational approximation of the spectral projector and can achieve high accuracy with few trapezoidal-rule nodes.This is attributed to exponential convergence for analytic functions.
Scope: The results establish exponential decay for zero-temperature gapped systems and positive-temperature systems with arbitrary finite-range Hamiltonians.The paper presents this as a broad mathematical foundation for nearsightedness.

8.9. Computational considerations.

Decay estimates can guide sparse approximations of density matrices, but their practical usefulness is limited by conservative worst-case assumptions and the need for spectral information.

Computational use: Exponential decay implies that only O(n) entries of each approximation need exceed any fixed threshold δ > 0.This supports prescribing sparsity patterns before computation and controlling storage requirements.
Computational use: Decay estimates can determine truncation bandwidths for Chebyshev approximations of finite-temperature density matrices at a prescribed error tolerance.The estimates are applied to the Fermi–Dirac matrix function before evaluating the polynomial approximation.
Limitations: The bounds are generally pessimistic, especially at zero or low temperatures, because they ignore numerical cancellation and variation in Hamiltonian-entry magnitudes.They are derived from worst-case polynomial-approximation degree estimates.
Limitations: The theory’s bounds depend essentially on the spectral gap γ for a fixed sparsity pattern and do not use detailed eigenvalue distributions.Additional Hamiltonian assumptions or spectral information could improve the bounds but would reduce generality.
Limitations: Applying the bounds requires lower and upper spectral bounds, an estimate of the gap, and the Fermi level μ.The paper notes that O(n) procedures can obtain sufficiently accurate estimates of these quantities.
Computational use: The orthogonalization analysis preserves a system-size-independent decay rate, although transformed matrices may have different decay constants.This supports treating orthonormal representations within the same asymptotic framework.

9. Transformation to an orthonormal basis.

Transforming a non-orthogonal Hamiltonian to an orthogonal basis preserves exponential off-diagonal decay under uniformly well-conditioned overlap matrices, enabling uniformly sparse approximations.

Overlap factors: Uniformly bounded condition numbers and bounded bandwidths for overlap matrices yield uniform exponential decay for their inverses and inverse square roots.The decay constants and prefactors remain independent of matrix size.
Decay under transformation: The transformed Hamiltonian ˜H_n = Z_n^T H_n Z_n inherits exponential off-diagonal decay from H_n and the overlap factor Z_n.The result extends directly from two-factor products to the three-factor transformation.
Decay under transformation: For matrices with exponential decay, products retain exponential decay at any reduced rate α′ < α with a size-independent constant.This result is applied to products involving Hamiltonians and overlap factors.
Sparse approximation: Banded approximations of H_n and Z_n can produce uniformly accurate approximations of the transformed Hamiltonian by reducing factor-approximation errors.The construction can include further truncation while achieving any prescribed tolerance.
Numerical illustration: For the C52H106 alkane, orthogonalization slightly widens the Hamiltonian bandwidth at tolerance 10^-8 when the overlap matrix is well-conditioned.The figure compares non-orthogonal and orthogonal representations using entry-magnitude color bands.
Choice of factor: The inverse Cholesky factor offers triangular structure and reorderings that can increase sparsity, whereas the Löwdin factor is full but often has a smaller multiplicative constant.The paper reports little practical difference in observed decay between the two factors.

10. The vanishing gap case.

When the spectral gap vanishes, zero-temperature density matrices can decay only slowly despite localized-looking structure, making linear-scaling approximations difficult; positive temperature restores exponential decay in the analyzed model.

Limitations: Zero-temperature bounds lose meaning as the gap tends to zero because the Fermi–Dirac approximation becomes discontinuous.A general treatment of the vanishing-gap case is described as difficult.
Vanishing gap: Only linear decay bounds hold in the one-dimensional model, producing a large prefactor for O(n) approximations and a formidable challenge when the gap vanishes.The example is presented as a simple model of metallic behavior.
Vanishing gap: The model’s spectral gap vanishes as system size grows, while its eigenvectors are strongly delocalized.Nevertheless, density-matrix localization can arise from cancellation or destructive interference.
Vanishing gap: The finite-section projectors converge strongly to an infinite-dimensional orthogonal projector even though the limiting operator has no eigenvalues and the finite gaps vanish.The theorem characterizes the limiting spectrum as [−1, 1] and the projector as χ_[−1,0)(H).
Higher-dimensional structure: In the two-dimensional extension, diagonal blocks equal 1/2 I_n, while off-diagonal blocks retain a striped structure and the same essential decay rate as in one dimension.The three-dimensional case is stated to lead to the same conclusion.
Positive temperature: At positive temperature, Chebyshev coefficients of the analytic Fermi–Dirac function decay exponentially, implying exponential decay of density-matrix entries.The decay becomes faster as temperature increases, and the rate can be estimated numerically from the coefficients.

11. Other applications.

The paper applies decay bounds for matrix functions to thermal density matrices, complex networks, eigensolvers, and related quantum systems. These applications connect localization estimates with correlations, approximation, and computational cost.

11.1. Density matrices for thermal states.: At high temperature, the canonical density matrix approaches the identity divided by n, so off-diagonal entries vanish and states become uncorrelated.At zero temperature, it approaches the orthogonal projector associated with the zero-energy eigenspace.
11.1. Density matrices for thermal states.: At positive temperature, the canonical density matrix is full but decays away from the main diagonal or the sparsity pattern of H.The decay rate depends on β, with smaller β producing faster decay.
Other applications.: Exponential decay bounds for matrix functions also support studies of spectral gaps, correlation decay, entanglement area laws, disordered systems, and Lanczos error estimates.These applications extend the theory beyond electronic-structure density matrices.
11.3. Complex networks.: Matrix-function decay bounds can estimate communicability and related quantities in sparse complex networks, but uniform exponential rates may fail for scale-free graphs without additional structure.The obstruction is that maximum degree grows with network size.
11.4. Tridiagonal eigensolvers.: Localization in invariant subspaces for isolated eigenvalue clusters can support banded spectral-projector approximations with prescribed error in symmetric tridiagonal eigensolvers.Whether these estimates yield substantially faster practical algorithms remains open.

12. Conclusions and open problems.

The conclusions establish exponential localization bounds for zero-temperature gapped systems and positive-temperature systems, while identifying slow decay as a fundamental obstacle for zero-temperature metals. The paper also outlines alternative representations and approximation strategies for that metallic regime.

Conclusions.: The theory gives exponential off-diagonal decay bounds for zero-temperature density matrices of gapped systems and for positive-temperature density matrices.It also addresses banded and sparse approximations, non-orthogonal basis transformations, and orthogonal projectors.
Conclusions.: The bounds capture the correct asymptotics for small gaps and low temperatures, providing theoretical support for O(n) electronic-structure methods.This conclusion is stated for the regimes covered by the theory.
Open problems.: When temperature is zero and the gap vanishes, the bounds deteriorate as n increases and no longer remain exponentially decaying as n →∞.For zero-temperature metals, spectral-projector decay follows a power law.
Open problems.: Slow decay makes O(n) methods problematic for zero-temperature metals, leaving the problem essentially open.The paper suggests localized occupied-subspace factors, rank-structured approximations, tensor products, and wavelets as alternatives.