论文标题
分析探测技术的稀疏近似和痕量估计腐烂矩阵函数的痕量估计
Analysis of probing techniques for sparse approximation and trace estimation of decaying matrix functions
论文作者
论文摘要
矩阵函数的计算$ f（a）$或相关数量（如其跟踪）是一项重要但具有挑战性的任务，尤其是对于大而稀疏的矩阵$ a $。近年来，在这种情况下，探测方法已成为经常被考虑的工具，因为它们允许通过评估（少数）$ f（a）v $或$ v $或$ v^tf（a）V $的评估来替换$ f（a）$或$ \ text {tr}（f（a））$的计算。然后，可以通过标准技术有效地解决这些任务，例如Krylov子空间方法。众所周知，当$ f（a）$大约稀疏时，探测方法特别有效，例如，当$ f（a）$的条目显示出强大的脱离脱节衰减时，但是到目前为止缺乏严格的错误分析。在本文中，我们开发了有关$ f（a）$的稀疏近似值的新理论结果，以及基于图形颜色探测方法的错误界。作为副产品，通过仔细检查这些错误范围的证据，我们还获得了新的见解，以便何时停止用于近似$ f（a）v $或$ v^tf（a）v $的Krylov迭代，从而允许实际上有效地实施探测方法。
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.
