zbMATH — the first resource for mathematics

Decay bounds and \(O(n)\) algorithms for approximating functions of sparse matrices. (English) Zbl 1171.65034
Summary: 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.

65F30 Other matrix algorithms (MSC2010)
65F50 Computational methods for sparse matrices
15A54 Matrices over function rings in one or more variables
65F40 Numerical computation of determinants
15A15 Determinants, permanents, traces, other special matrix functions
Full Text: EMIS EuDML