  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 $\lceil n/2\rceil$
matrix-vector products, thus substantially reducing the cost of existing trace
estimation algorithms that use Chebyshev interpolation or Taylor series.
