Fast computation of spectral densities for generalized eigenvalue problems

Yuanzhe Xi, Ruipeng Li, Yousef Saad

Research output: Contribution to journalArticlepeer-review

11 Scopus citations


The distribution of the eigenvalues of a Hermitian matrix (or of a Hermitian matrix pencil) reveals important features of the underlying problem, whether a Hamiltonian system in physics or a social network in behavioral sciences. However, computing all the eigenvalues explicitly is prohibitively expensive for real-world applications. This paper presents two types of methods to efficiently estimate the spectral density of a matrix pencil (A, B) where both A and B are sparse Hermitian and B is positive definite. The methods are targeted at the situation when the matrix B scaled by its diagonal is very well conditioned, as is the case when the problem arises from some finite element discretizations of certain partial differential equations. The first method is an adaptation of the kernel polynomial method (KPM) and the second is based on Gaussian quadrature by the Lanczos procedure. By employing Chebyshev polynomial approximation techniques, we can avoid direct factorizations in both methods, making the resulting algorithms suitable for large matrices. Under some assumptions, we prove bounds that suggest that the Lanczos method converges twice as fast as the KPM method. Numerical examples further indicate that the Lanczos method can provide more accurate spectral densities when the eigenvalue distribution is highly nonuniform. As an application, we show how to use the computed spectral density to partition the spectrum into intervals that contain roughly the same number of eigenvalues. This procedure, which makes it possible to compute the spectrum by parts, is a key ingredient in the new breed of eigensolvers that exploit ``spectrum slicing.""

Original languageEnglish (US)
Pages (from-to)A2749-A2773
JournalSIAM Journal on Scientific Computing
Issue number4
StatePublished - 2018
Externally publishedYes

Bibliographical note

Publisher Copyright:
© 2018 Society for Industrial and Applied Mathematics.


  • Chebyshev approximation
  • Density of states
  • Generalized eigenvalue problems
  • Perturbation theory
  • Spectral density
  • Spectrum slicing


Dive into the research topics of 'Fast computation of spectral densities for generalized eigenvalue problems'. Together they form a unique fingerprint.

Cite this