Analysis of Probing Techniques for Sparse Approximation and Trace Estimation of Decaying Matrix Functions
Andreas Frommer, Claudia Schimmel, Marcel Schweitzer · SIAM Journal on Matrix Analysis and Applications · 2021
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 one to replace the computation of $f(A)$ or 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 quantities can then be efficiently computed 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.