  The implicit trace estimation problem asks for an approximation of the trace
of a square matrix, accessed via matrix-vector products (matvecs). This paper
designs new randomized algorithms, XTrace and XNysTrace, for the trace
estimation problem by exploiting both variance reduction and the
exchangeability principle. For a fixed budget of matvecs, numerical experiments
show that the new methods can achieve errors that are orders of magnitude
smaller than existing algorithms, such as the Girard-Hutchinson estimator or
the Hutch++ estimator. A theoretical analysis confirms the benefits by offering
a precise description of the performance of these algorithms as a function of
the spectrum of the input matrix. The paper also develops an exchangeable
estimator, XDiag, for approximating the diagonal of a square matrix using
matvecs.
