  The computation of matrix functions $f(A)$, or related quantities like their
trace, is an important but challenging task, in particular for large and sparse
matrices $A$. In recent years, probing methods have become an often considered
tool in this context, as they allow to replace the computation of $f(A)$ or
$\text{tr}(f(A))$ by the evaluation of (a small number of) quantities of the
form $f(A)v$ or $v^Tf(A)v$, respectively. These tasks can then efficiently be
solved by standard techniques like, e.g., Krylov subspace methods. It is
well-known that probing methods are particularly efficient when $f(A)$ is
approximately sparse, e.g., when the entries of $f(A)$ show a strong
off-diagonal decay, but a rigorous error analysis is lacking so far. In this
paper we develop new theoretical results on the existence of sparse
approximations for $f(A)$ and error bounds for probing methods based on graph
colorings. As a by-product, by carefully inspecting the proofs of these error
bounds, we also gain new insights into when to stop the Krylov iteration used
for approximating $f(A)v$ or $v^Tf(A)v$, thus allowing for a practically
efficient implementation of the probing methods.
