Source-linked AI summary
Efficient estimation of eigenvalue counts in an interval
Edoardo Di Napoli, Eric Polizzi, Yousef Saad
TL;DR
Counting eigenvalues in an interval matters for selecting subspace sizes in large sparse eigensolvers, but exact inertia-based counts can be expensive. The paper develops stochastic trace estimates using polynomial and rational approximations to the spectral projector, finding that these methods can replace costly factorizations when approximate counts suffice.
Problem
Approximate eigenvalue counts are needed for interval-based eigensolvers, while exact inertia counting can be too costly for large three-dimensional sparse or dense problems.
Method
The paper estimates the trace of an interval spectral projector with stochastic estimators after approximating the projector using polynomial or rational functions.
Results
The methods provide inexpensive approximate counts, and rational filtering can use iterative solves with a minimum but not high solver accuracy.
Takeaways & Limitations
Approximate projector-trace counts can initialize eigensolvers such as FEAST by determining an appropriate search-subspace size.
Takeaways & Limitations
Count accuracy depends on projector approximation and can be strongly affected by clustered eigenvalues near interval boundaries.
Abstract
from arXiv · showhide
Estimating the number of eigenvalues located in a given interval of a large sparse Hermitian matrix is an important problem in certain applications and it is a prerequisite of eigensolvers based on a divide-and-conquer paradigm. Often an exact count is not necessary and methods based on stochastic estimates can be utilized to yield rough approximations. This paper examines a number of techniques tailored to this specific task. It reviews standard approaches and explores new ones based on polynomial and rational approximation filtering combined with a stochastic procedure.
1 Introduction
The paper motivates approximate eigenvalue counts for spectrum-slicing eigensolvers and reviews exact inertia-based counting alongside cheaper stochastic polynomial and rational alternatives.
- Motivation: Spectrum splitting requires approximate eigenvalue counts to choose subspace dimensions for interval-based eigensolvers.The count supports independent extraction of eigenpairs from spectral intervals and selection of subspace sizes.
- Traditional approach: Sylvester inertia gives an exact interval count from the difference between Sturm counts for shifted matrices A −aI and A −bI.The method uses LDLT factorizations to count eigenvalues above each endpoint.
- Traditional approach: The exact approach requires two complete LDLT factorizations, which can be expensive for realistic eigenproblems.This motivates methods that provide estimates rather than exact counts.
- Alternative methods: Two alternative methods estimate the trace of the interval spectral projector using stochastic trace estimators.The projector is approximated either polynomially or rationally as a function of A.
- Related methods: Polynomial filtering uses Chebyshev-based spectrum slicing, while rational filtering uses contour-integral eigen-projectors and requires a sufficiently sized invariant subspace.Implementation choices include barrier or high/low-pass filters, LU factorizations, and Krylov methods.
2 Eigenvalue counts
The eigenvalue count equals the trace of an interval spectral projector, enabling stochastic estimation through polynomial or rational approximations instead of costly factorizations. Accuracy is governed mainly by projector approximation, while trace-estimator convergence can require sample counts related to the projector trace.
- Counting difficulty: The standard inertia count can become prohibitively costly for large three-dimensional sparse or dense problems because factorization creates substantial fill-in.The approach remains viable for smaller dense matrices or sparse matrices whose factorizations are inexpensive.
- Projector formulation: The paper estimates the interval count by approximating the trace of the corresponding spectral projector.Because a projector has eigenvalues zero or one, its trace equals the number of eigenvalues in the interval.
- Approximation methods: The unavailable projector is approximated as either a Chebyshev-polynomial or rational function of A, then evaluated with stochastic trace estimators.The rational form arises from contour integration, while the polynomial form approximates the projector as ψ(A).
- Stochastic estimation: Hutchinson-style estimation averages quadratic forms v_k^T A v_k from independent random vectors to approximate a matrix trace.Rademacher vectors are unbiased; Gaussian vectors are also possible, with different variance and convergence behavior.
- Estimator behavior: The trace estimator may converge with nv ≲ tr(P), but projector-approximation bias often dominates the stochastic trace-estimation error.A stated sample-complexity lemma gives a looser bound with a large prefactor proportional to tr(P).
- Computational trade-offs: Polynomial filtering avoids factorization, whereas rational filtering needs linear solves that can use low-accuracy iterative methods.The resulting count error depends mainly on projector approximation and can be strongly affected by clustered eigenvalues near interval boundaries.
3 Polynomial expansion filtering
Polynomial filtering approximates the spectral projector with Chebyshev expansions and estimates its trace stochastically. The approach extends to generalized eigenproblems through high-pass filters and inertia-based transformations, but convergence and error control remain difficult near discontinuities and spectral clusters.
- Polynomial approximation: The step function defining the spectral projector is expanded into degree-p Chebyshev polynomials, yielding a matrix approximation built from T_j(A).The expansion assumes eigenvalues are scaled into [−1, 1], using estimates that safely enclose the smallest and largest eigenvalues.
- Polynomial approximation: Jackson coefficients damp Gibbs oscillations near the discontinuities of the step function, producing a smoothed approximation instead of the standard Chebyshev expansion.The Jackson expansion can be viewed as approximating degree-dependent smoothed versions of the original function.
- Stochastic estimation: The polynomial trace estimate requires only matrix-vector products, with Chebyshev vectors generated efficiently by a three-term recurrence.The resulting stochastic estimator substitutes the polynomial projector approximation into Hutchinson-style trace estimation.
- Theoretical considerations: Polynomial filtering lacks uniform convergence for the standard Chebyshev approximation, while smoothing introduces a second degree-dependent approximation target.For generalized problems, the spectrum of A −σB can also require a very large polynomial degree in some cases.
- Theoretical considerations: The standard Chebyshev error bound converges like 1/√p, while most inaccuracy is concentrated around the jumps of the step function.The polynomial is explicit, so its error can be examined on specific subintervals at modest degree.
- Generalized eigenvalue problem: For generalized problems, the interval count can be written as µ[a, b] = µa − µb, where µa and µb count positive eigenvalues of A −aB and A −bB.The inertia equivalence in Proposition 3.2 supplies the basis for avoiding a direct transformation through a costly Cholesky factorization.
4 Rational expansion filtering
Rational filtering represents the spectral projector through a Cauchy integral and estimates its trace using sampled resolvent solves. Its practical cost can be reduced through reused factorizations or Krylov methods, but accuracy depends on contour placement, search-space size, and solver tolerances.
- Approximations for the spectral projector: The spectral projector is represented by a Cauchy integral of the resolvent over a contour enclosing the desired spectrum, typically a circle with diameter [a, b].Numerical quadrature replaces the integral with weighted resolvent evaluations at integration points.
- Approximations for the spectral projector: The rational projector approximation is combined with stochastic trace estimation by averaging quadratic forms (Pv, v) over random vectors.This yields an approximate eigenvalue count without explicitly forming the projector.
- Approximations for the spectral projector: For generalized eigenproblems, each standard resolvent (A −z_jI)^−1 is replaced by (A −z_jB)^−1B, requiring multiple-right-hand-side linear solves.The method can reuse factorizations of shifted systems, though those factorizations need not be exact.
- Approximations for the spectral projector: Rational filtering is especially suited to FEAST when the shifted factorizations are already available for subspace iteration.The same quadrature points along the half-circle can support both FEAST and the rational count estimate.
- Approximations for the spectral projector: The count and FEAST convergence can degrade when an interval boundary lies near a spectral cluster or when the search-space size M0 is too close to µ[a, b].The rational-function ratio is expected to decrease exponentially with the number of integration points, but may increase near clusters.
- Practical considerations: Krylov methods can solve shifted systems for different integration points using a common Krylov subspace, while solver accuracy should be controlled by residual reduction rather than a fixed iteration count.A residual norm reduction such as 10^−2 is given as an example of a consistent criterion.
5 Numerical experiments
Numerical experiments show that polynomial and rational stochastic filters can estimate eigenvalue counts, but accuracy depends on spectral clustering, polynomial degree, sample-vector count, solver accuracy, and memory constraints.
- 5.1 Polynomial filtering: Standard and Jackson polynomials: For Na5, the exact count was 100, while degree-70 Chebyshev and Jackson-Chebyshev estimates were 101.25 and 102.20, respectively.The same random-vector sequence was used for both methods.
- 5.2 Estimate bias: Polynomial projector approximations may require a relatively large degree, because insufficient degree can produce substantial trace errors.The trace of the approximate projector is not generally equal to the eigenvalue count.
- 5.3 Eigenvalue clustering: Intervals intersecting the beginning of an eigenvalue cluster overestimate counts, whereas intervals intersecting the cluster end underestimate them.The error depends on cluster length and relative eigenvalue spacing, and the same qualitative bias occurs for rational expansions.
- 5.4 Number of sample vectors and estimator accuracy: Estimate oscillations became consistently smaller than one for 50 ≤ nv ≤ 100 in the small case and 200 ≤ nv ≤ 300 in the larger case.For intervals containing only a few eigenvalues, nv approximately comparable to tr(P) may be needed; larger counts can require fewer vectors than tr(P).
- 5.5 Rational approximation filtering: Direct vs iterative solvers: For Na5 rational filtering, exact factorizations gave counts 98.64 with nc = 3 and 100.27 with nc = 5, while Sylvester inertia required only two direct factorizations.The inertia approach was reported as much faster in this example.
- 5.5 Rational approximation filtering: Direct vs iterative solvers: GMRES produced Na5 counts of 75.35, 97.61, and 98.65 for residual thresholds 10^-1, 10^-2, and 10^-3, with strong agreement to direct factorization at tighter thresholds.Rational accuracy incurred high memory costs for direct LU, while ILU reduced total nonzeros from 22,239,530 to 799,143; direct factorization became infeasible for the reported 3-D setting.
- 5.5 Rational approximation filtering: Direct vs iterative solvers: Insufficiently accurate GMRES and preconditioned GMRES underestimated eigenvalue counts by an approximately constant bias relative to the exact solver.The paper notes that this bias requires further investigation.
- 5.6 Using estimated eigenvalue counts in FEAST: The FEAST experiments use estimated counts to size search subspaces, with convergence governed by the subspace size and rational-filter value beyond the target interval.The reported results include linear convergence for nc = 8 and convergence rates consistent with the expected behavior.
6 Conclusion
The proposed eigenvalue-counting methods trade accuracy against speed: exact inertia-based counts may be costly, while stochastic polynomial or rational projector approximations can be cheaper. Their estimates may be biased when projector approximations are inaccurate, especially near clustered interval boundaries.
- Exact counting via the Sylvester inertia theorem may be preferable when accuracy is essential, but direct factorization can be costly or impractical.
- Stochastic trace estimates using polynomial or rational expansions provide cheaper approximate counts when an exact count is unnecessary.
- Rational approximation can fit FEAST because approximate factorizations are already needed, keeping eigenvalue-count initialization cost relatively small.
- Approximate spectral projectors introduce bias, which can worsen when eigenvalue clusters lie near interval boundaries.
- Reducing this bias remains an open issue for future investigation.