Fast computation of spectral densities for generalized eigenvalue problems

Yuanzhe Xi, Ruipeng Li, Yousef Saad

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

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
Volume40
Issue number4
DOIs
StatePublished - 2018

Bibliographical note

Funding Information:
\ast Submitted to the journal's Methods and Algorithms for Scientific Computing section June 20, 2017; accepted for publication (in revised form) July 12, 2018; published electronically August 30, 2018. http://www.siam.org/journals/sisc/40-4/M113554.html Funding: The first and third author's work was supported in part (applications and practical aspects) by the Scientific Discovery through Advanced Computing (SciDAC) program funded by U.S. Department of Energy, Office of Science, Advanced Scientific Computing Research and Basic Energy Sciences DE-SC0008877, and in part (theory) by NSF under grant CCF-1505970. The second author's work was performed under the auspices of the U.S. Department of Energy by Lawrence Livermore National Laboratory under Contract DE-AC52-07NA27344 (LLNL-JRNL-744480).

Keywords

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

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

Cite this