Spectrum-Adapted Polynomial Approximation for Matrix Functions

Abstract

We propose and investigate two new methods to approximate $f(\mathbf{A})\mathbf{b}$ for large, sparse, Hermitian matrices $\mathbf{A}$. The main idea behind both methods is to first estimate the spectral density of $\mathbf{A}$, and then find polynomials of a fixed order that better approximate the function $f$ on areas of the spectrum with a higher density of eigenvalues. Compared to state-of-the-art methods such as the Lanczos method and truncated Chebyshev expansion, the proposed methods tend to provide more accurate approximations of $f(\mathbf{A})\mathbf{b}$ at lower polynomial orders, and for matrices $\mathbf{A}$ with a large number of distinct interior eigenvalues and a small spectral width.