Fast computation of spectral densities for generalized eigenvalue problems

DOI10.1137/17M1135542zbMATH Open1416.65097arXiv1706.06610OpenAlexW2962939379WikidataQ129270940 ScholiaQ129270940MaRDI QIDQ4584929FDOQ4584929

Authors: Yuanzhe Xi, Ruipeng Li, Y. Saad 

Publication date: 5 September 2018

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

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)$ when both $A$ and $B$ are Hermitian and, in addition, $B$ is positive definite. The first one is based on the Kernel Polynomial Method (KPM) and the second 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 non-uniform. 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".

Full work available at URL: https://arxiv.org/abs/1706.06610

Recommendations

• Computing the eigenvalues of symmetric \(\mathcal{H}^2\)-matrices by slicing the spectrum
• A spectral Newton-Schur algorithm for the solution of symmetric generalized eigenvalue problems
• Randomized estimation of spectral densities of large matrices made accurate
• Efficient estimation of eigenvalue counts in an interval.
• Spectral Schur complement techniques for symmetric eigenvalue problems

zbMATH Keywords

spectral densityperturbation theorydensity of statesspectrum slicingChebyshev approximationgeneralized eigenvalue problems

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Eigenvalues, singular values, and eigenvectors (15A18) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Iterative numerical methods for linear systems (65F10)

Cites Work

• Algorithm 837
• Functions of Matrices
• Matrix Analysis
• A fast algorithm for particle simulations
• Numerical methods for large eigenvalue problems
• A filtered Lanczos procedure for extreme and interior eigenvalue problems
• Approximation theory and approximation practice
• Calculation of Gauss Quadrature Rules
• A Stochastic Estimator of the Trace of the Influence Matrix for Laplacian Smoothing Splines
• Title not available (Why is that?)
• A probing method for computing the diagonal of a matrix inverse.
• Chebyshev semi-iteration in preconditioning for problems including the mass matrix
• The kernel polynomial method
• Spectral Schur complement techniques for symmetric eigenvalue problems
• Self-consistent-field calculations using Chebyshev-filtered subspace iteration
• Bounding the spectrum of large Hermitian matrices
• A spectrum slicing method for the Kohn-Sham problem
• Kernel polynomial approximations for densities of states and spectral functions
• A QUANTITATIVE FORMULATION OF SYLVESTER'S LAW OF INERTIA
• Realistic Eigenvalue Bounds for the Galerkin Mass Matrix
• Matrix pseudo-spectroscopy: Iterative calculation of matrix eigenvalues and eigenvectors of large matrices using a polynomial expansion of the Dirac delta function
• Approximating spectral densities of large matrices
• Randomized estimation of spectral densities of large matrices made accurate
• Conditioning of finite element equations with arbitrary anisotropic meshes
• A thick-restart Lanczos algorithm with polynomial filtering for Hermitian eigenvalue problems
• Computing partial spectra with least-squares rational filters
• An empirical comparison of graph Laplacian solvers
• Computing \(f(A)b\) via least squares polynomial approximations
• Improving the incoherence of a learned dictionary via rank shrinkage
• SMASH: structured matrix approximation by separation and hierarchy.

Cited In (11)

• Generalized spectrum approximation and numerical computation of eigenvalues for Schrödinger's operators
• Fast and stable schemes for phase fields models
• Title not available (Why is that?)
• Localized spectrum slicing
• Eigenvalue computations in the context of data-sparse approximations of integral operators
• Approximating spectral densities of large matrices
• Stochastic algorithms for self-consistent calculations of electronic structures
• A parallel algorithm for computing partial spectral factorizations of matrix pencils via Chebyshev approximation
• Computing the eigenvalues of symmetric \(\mathcal{H}^2\)-matrices by slicing the spectrum
• Computational procedure for a fast calculation of eigenvectors and eigenvalues of structures with random properties
• The eigenvalues slicing library (EVSL): algorithms, implementation, and software

Uses Software

• AMD

This page was built for publication: Fast computation of spectral densities for generalized eigenvalue problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4584929)