Faster stochastic trace estimation with a Chebyshev product identity
Faster stochastic trace estimation with a Chebyshev product identity
复制标题
使用切比雪夫产品恒等式更快地进行随机迹线估计
DOI：
10.1016/j.aml.2021.107246
复制
发表时间：
2021
影响因子：
3.7
通讯作者：
Hallman, Eric
中科院分区：
文献类型：
--
作者：
Hallman, Eric
随机迹估计的方法通常需要重复计算形式为z T p n(A)z的表达式，其中A是对称矩阵，p n是以标准基或切比雪夫基写成的n次多项式。我们展示了如何仅使用⌈n/2⌉矩阵向量积来计算这些表达式，从而大大降低了现有使用切比雪夫插值或泰勒级数的迹估计算法的成本。
Methods for stochastic trace estimation often require the repeated evaluation of expressions of the form z T p n (A) z, where A is a symmetric matrix and p n is a degree n polynomial written in the standard or Chebyshev basis. We show how to evaluate these expressions using only⌈ n∕ 2⌉ matrix–vector products, thus substantially reducing the cost of existing trace estimation algorithms that use Chebyshev interpolation or Taylor series.