Session III.1 - Numerical Linear Algebra
Monday, June 19, 14:30 ~ 15:00
XTrace: Making the most of every sample in stochastic trace estimation
Joel Tropp
Caltech, USA - This email address is being protected from spambots. You need JavaScript enabled to view it.
The implicit trace estimation problem asks for an approximation of the trace of a square matrix, accessed via matrix--vector products (matvecs). This talk introduces new randomized algorithms, \textsc{XTrace} and \textsc{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. 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.
Available from arXiv:2301.07825.
Joint work with Ethan N. Epperly (Caltech) and Robert J. Webber (Caltech).