Volume 28, pp. 16-39, 2007-2008.

Decay bounds and $O$($n$) algorithms for approximating functions of sparse matrices

Michele Benzi and Nader Razouk

Abstract

We establish decay bounds for the entries of $f(A)$, where $A$ is a sparse (in particular, banded) $n\times n$ diagonalizable matrix and $f$ is smooth on a subset of the complex plane containing the spectrum of $A$. Combined with techniques from approximation theory, the bounds are used to compute sparse (or banded) approximations to $f(A)$, resulting in algorithms that under appropriate conditions have linear complexity in the matrix dimension. Applications to various types of problems are discussed and illustrated by numerical examples.

Full Text (PDF) [1.5 MB], BibTeX

Key words

Matrix functions, sparse and banded matrices, decay rates, linear time algorithms, Chebyshev polynomials, Faber polynomials, density matrix, trace, determinant

AMS subject classifications

Primary 65F10, 65F30. Secondary 15A.

ETNA articles which cite this article

Vol. 48 (2018), pp. 362-372 Andreas Frommer, Claudia Schimmel, and Marcel Schweitzer: Non-Toeplitz decay bounds for inverses of Hermitian positive definite tridiagonal matrices

Vol. 55 (2022), pp. 438-454 Marcel Schweitzer: Decay bounds for Bernstein functions of Hermitian matrices with applications to the fractional graph Laplacian

Vol. 58 (2023), pp. 538-567 Shengjie Xu and Fei Xue: Inexact rational Krylov subspace methods for approximating the action of functions of matrices