Faster stochastic trace estimation with a Chebyshev product identity

摘要

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 inverted right perpendicularn/2inverted left perpendicular matrix-vector products, thus substantially reducing the cost of existing trace estimation algorithms that use Chebyshev interpolation or Taylor series. (C) 2021 Elsevier Ltd. All rights reserved.