  In applications, we often need to compute functions of matrices, such as
banded matrices, the Kronecker sum of banded matrices, Toeplitz matrices, and
many other types, which all share the common feature that their non-zero
elements are concentrated around certain diagonals. We approximate matrix
functions by considering the positions of non-zero diagonals in the original
matrix. Focusing on non-zero diagonals provides us with simple algorithms to be
used as tools to reduce complexity of other algorithms for computing matrix
functions. Here, we first establish a decay bound for elements of matrix
functions using the non-zero diagonals. Then, we develop methods that involve
dividing the problem of computing matrix functions into functions of some
submatrices of the original matrix. The size of these submatrices depends on
the positions and number of non-zero diagonals in a monomial of the original
matrix, ranging from degree zero to a given degree. For Toeplitz matrices, we
demonstrate that our method turns to a simpler algorithm and works more
efficiently. The convergence analysis of our proposed methods is conducted by
establishing connections to the best polynomial approximation. When only
specific elements or the trace of matrix functions are required, we derive
submatrices from the original matrix based solely on the indices of the
elements of interest. Additionally, for the special case of banded-symmetric
Toeplitz matrices, we derive an approximation for elements of matrix functions
with geometrically reducing error, using closed-form formulas that depend
solely on the indices of the elements.
