View abstract

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).

View abstract PDF