PaperlayerView exact revision on arXiv

Source-linked AI summary

Approximating spectral densities of large matrices

Lin Lin, Yousef Saad, Chao Yang

arXiv:1308.5467v2math.NA

TL;DR

Estimating the spectral density of a large real symmetric matrix is difficult because exact eigenvalue computation is costly. The paper surveys matrix-vector-based methods, formalizes resolution-aware accuracy assessment, and reports that Lanczos consistently gives the most accurate approximations in its numerical tests, especially with few MATVECs.

  • Problem

    Exact computation of a large matrix’s spectrum is prohibitively expensive, motivating DOS estimation without computing all eigenvalues.

  • Method

    The paper surveys KPM, Lanczos-based, and Haydock-based approaches, including polynomial expansions, regularization, and matrix-vector operations.

  • Results

    Lanczos consistently outperforms the other methods in approximation accuracy, especially when few MATVECs are used.

  • Takeaways & Limitations

    Regularization and resolution-aware error metrics provide a rigorous framework for comparing spectral-density approximations.

  • Takeaways & Limitations

    KPM and its variants are less effective for DOS functions with many peaks or spectra containing large gaps.

Abstract

from arXiv · show

In physics, it is sometimes desirable to compute the so-called \emph{Density Of States} (DOS), also known as the \emph{spectral density}, of a real symmetric matrix $A$. The spectral density can be viewed as a probability density distribution that measures the likelihood of finding eigenvalues near some point on the real line. The most straightforward way to obtain this density is to compute all eigenvalues of $A$. But this approach is generally costly and wasteful, especially for matrices of large dimension. There exists alternative methods that allow us to estimate the spectral density function at much lower cost. The major computational cost of these methods is in multiplying $A$ with a number of vectors, which makes them appealing for large-scale problems where products of the matrix $A$ with arbitrary vectors are relatively inexpensive. This paper defines the problem of estimating the spectral density carefully, and discusses how to measure the accuracy of an approximate spectral density. It then surveys a few known methods for estimating the spectral density, and proposes some new variations of existing methods. All methods are discussed from a numerical linear algebra point of view.

1. Introduction.

The paper frames spectral-density estimation as a large-matrix problem where exact eigenvalue computation is costly, and develops matrix-vector-based alternatives with rigorous accuracy evaluation.

  • The DOS represents the probability of finding eigenvalues near a point on the real line.
  • Computing the complete spectrum is prohibitively expensive for large matrices, motivating efficient alternatives that estimate the DOS without computing eigenvalues.
  • Histogramming eigenvalues through inertia counts is impractical because it requires many costly LDLT factorizations.
  • The paper reviews KPM and related polynomial methods, connects Lanczos spectroscopic sampling to KPM, and presents the Delta-Gauss-Legendre variant.
  • The surveyed methods rely on matrix-vector products, making comparable MATVEC counts central to method selection.
  • Its proposed accuracy measure accounts for desired resolution, enabling rigorous quantitative comparisons rather than subjective visual judgments.

2. Assessing the quality of spectral density approximation.

The paper addresses the difficulty of measuring errors against a distribution-valued DOS by restricting resolution or regularizing Dirac functions into smooth densities. The resulting framework makes approximation quality quantitatively meaningful while exposing a resolution–detail trade-off.

  • Standard Lp-norms cannot directly measure error against a DOS defined by Dirac distributions.
  • The paper uses test functions from a restricted Schwartz subspace to define finite-resolution error measurements.
  • Regularizing Dirac functions with Gaussians produces a continuous spectral density φσ for which L1, L2, and L∞ errors are meaningful.
  • No smooth approximation can converge to the Dirac-defined DOS at infinite resolution, so finite-resolution goals are essential.
  • The error metric can be viewed as the L∞ error between blurred exact and approximate spectral densities.
  • Gaussian regularization interprets σ as resolution: larger σ produces smoother curves but can erase local spectral detail, while smaller σ preserves peaks but yields rougher curves.
  • Lorentzian regularization offers an alternative whose width is controlled by η and underlies Haydock’s method.
  • Preserving non-negativity matters because methods that violate it can incur large numerical error.

3. Numerical methods for estimating spectral density.

The paper surveys two classes of stochastic, matrix–vector-product methods for approximating spectral density: polynomial expansions and Lanczos-based methods with regularization. It connects several approaches, describes their computational mechanisms, and highlights trade-offs involving accuracy, flexibility, oscillation, and non-negativity.

  • Method classes: The methods comprise polynomial approaches, including KPM and related expansions, and Lanczos methods that regularize Ritz values with Gaussian or Lorentzian blurring.All methods use stochastic sampling and averaging to obtain approximate spectral densities.
  • Polynomial methods: KPM expands Dirac δ-functions in Chebyshev polynomials after scaling the eigenvalue interval to [−1, 1].Its coefficients are estimated from traces of Chebyshev matrix polynomials, using random-vector averages and a three-term recurrence.
  • Accuracy and trade-offs: KPM can exhibit Gibbs oscillations and lose non-negativity, whereas Lanczos-based approximations preserve non-negativity by construction.Jackson damping reduces oscillations but can oversmooth the density; Lanczos methods use regularized Ritz values and retain non-negativity.
  • Polynomial methods: The spectroscopic approach is essentially equivalent to KPM because both use Chebyshev-based representations of the spectral density.The paper interprets the spectroscopic coefficients through a transform of the spectral density.
  • Polynomial methods: The Delta-Chebyshev method evaluates traces of polynomial approximations, while the DGL method regularizes the Dirac δ-function with a Gaussian and expands it in Legendre polynomials.Both methods use stochastic matrix-function evaluations; DGL averages v^T h_Mi(A)v over normalized random vectors.
  • Polynomial methods: The Delta-Chebyshev method becomes identical to KPM when all sample points use the same polynomial degree, while varying degrees provides spectral flexibility without reducing the maximum MATVEC count.Different degrees can improve approximation in selected spectral regions, although matrix–vector products usually dominate cost.

4. Numerical results.

Numerical experiments compare DOS approximation methods across several matrices, using resolution-controlled error measures and direct regularized-DOS comparisons. Lanczos is generally most accurate, while damping and regularization create method-specific trade-offs.

  • Experimental setup: The experiments compare DOS approximations using resolution parameters and method-specific error metrics, with direct regularized-DOS comparisons for visual assessment.The target resolution is set through σ or η, and the same regularization footing is used when comparing exact and approximate DOS curves.
  • Modified Laplacian matrix: Lanczos outperforms the other methods on the modified Laplacian, especially for relatively small M.Jackson damping does not improve accuracy there because it can over-regularize sharp DOS peaks.
  • Modified Laplacian matrix: With M = 100 and nvec = 100, Lanczos is most accurate; Haydock produces broader peaks, while undamped KPM shows Gibbs oscillation and can become negative.Jackson damping preserves non-negativity but misses several peaks, whereas Lanczos and Haydock curves remain above zero.
  • Other test matrices: For shwater, Lanczos reaches 10^-3 accuracy with M = 50, whereas KPM without Jackson damping, KPML, and DGL require M > 110 terms.At M = 100, undamped KPM is accurate, while Jackson damping and Haydock introduce larger errors near peaks and valleys through extra smoothing or Lorentzian regularization.
  • Other test matrices: For pe3k, Lanczos is significantly more accurate than the other methods, while undamped KPM produces large oscillations and Jackson damping over-regularizes the approximation.The same pattern appears in the heat-capacity proof-of-principle: Lanczos has much smaller error than KPM for pe3k.
  • Application: Heat capacity calculation: Both KPM and Lanczos reproduce normalized heat capacity for the modified Laplacian, with Lanczos showing slightly smaller error.The computed heat-capacity values are used only as a proof of principle, with M = 40 MATVECs and averages over 100 runs.

5. Conclusion.

The paper surveys two classes of spectral-density approximations and finds that Lanczos is consistently the most accurate in numerical tests, especially with few MATVECs. It also identifies when KPM variants work well and how regularization supports quantitative error assessment.

  • The methods fall into KPM-based polynomial expansions and Lanczos-based approximations constructed from Ritz values with regularization.Lanczos and Haydock differ in their blurring functions, while DGL extends polynomial approaches with location-dependent degrees.
  • Gaussian regularization specifies approximation resolution and makes rigorous quantitative error measurement possible.
  • Lanczos consistently outperforms the other methods in accuracy, particularly when only a few MATVECs are available.
  • Lanczos and Haydock guarantee non-negative approximate DOS values and recover a regularized DOS when M = n.
  • KPM variants work well for relatively smooth DOS but are less effective for many peaks or large spectral gaps; Jackson damping can remove oscillations while missing important peaks.

Appendix A. Further discussion on the KPM method.

This appendix discusses KPM refinements based on damping, alternative orthogonal polynomials, and computational trade-offs in evaluating polynomial moments. It emphasizes that reducing matrix-vector products can require substantially more storage.

  • Jackson damping is used in KPM to reduce Gibbs oscillations by modulating the expansion coefficients.
  • KPM can use orthogonal polynomial families beyond Chebyshev, provided their three-term recurrences are explicitly known.Legendre polynomials are given as an example.
  • Moment computations can exploit products of lower-degree terms by storing vectors generated during the Chebyshev recurrence.
  • The alternative moment-evaluation strategy saves half of the matrix-vector products but requires storing all previous vectors, making it impractical for high-degree polynomials.

Appendix B. Details on the derivation of the DGL method.

The DGL derivation obtains expansion coefficients through Legendre-polynomial recurrences, integration, and initialization conditions. It also addresses recurrence stability by stopping when coefficients become sufficiently small.

  • DGL coefficients are derived from the three-term recurrence of Legendre polynomials and related integral identities.
  • The recurrence has no general closed-form coefficient formula, so the coefficients are computed recursively.
  • The coefficient recurrence uses γ−1 = 0 and initializes with γ0, ψ1 = γ0, and ψ0 = 0.
  • For large σ, coefficients can decay rapidly, and continuing the recurrence can become unstable.
  • The implementation selects an effective polynomial degree and avoids instability by stopping when coefficients fall below a tolerance such as 10−6.
  • The DGL approximation is formed by truncating the polynomial expansion to M + 1 terms.

Appendix C. Cumulative density of states from the Lanczos method.

The appendix develops a cumulative spectral-density alternative to directly approximating the DOS from an M-step Lanczos run. It uses monotonicity and sign-change properties to construct an interpolated, smoothed CDOS.

  • An approximate cumulative density of states can be constructed from an M-step Lanczos run using the tridiagonal matrix’s eigenvalues and eigenvector components.
  • The unregularized approximate CDOS is plotted as a staircase function for the modified 2D Laplacian.
  • Both the exact and approximate cumulative spectral densities are monotonically non-decreasing.
  • Their difference has precisely 2M − 1 sign changes within the spectrum, enabling interpolation at crossing points.
  • The interpolated CDOS matches the two cumulative densities where they cross and can then be smoothed to refine the spectral-density approximation.
Loading 1308.5467v2…