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

We establish decay bounds for the entries of f(A), where A is a sparse (in particular, banded) n × 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. Copyright © 2007, Kent State University.