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]

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.

< Back