  This work is concerned with approximating matrix functions for banded
matrices, hierarchically semiseparable matrices, and related structures. We
develop a new divide-and-conquer method based on (rational) Krylov subspace
methods for performing low-rank updates of matrix functions. Our convergence
analysis of the newly proposed method proceeds by establishing relations to
best polynomial and rational approximation. When only the trace or the diagonal
of the matrix function is of interest, we demonstrate -- in practice and in
theory -- that convergence can be faster. For the special case of a banded
matrix, we show that the divide-and-conquer method reduces to a much simpler
algorithm, which proceeds by computing matrix functions of small submatrices.
Numerical experiments confirm the effectiveness of the newly developed
algorithms for computing large-scale matrix functions from a wide variety of
applications.
