Title: Stochastic probing methods for estimating the trace of functions of sparse symmetric matrices, Speaker(s): Michele Rinelli, Scuola Normale Superiore, Date and time: 30 May 2023, 16:00 (Europe/Rome), Lecture series: Seminar on Numerical Analysis, Venue: Dipartimento di Matematica (Aula Riunioni).

You can access the full event here: https://events.dm.unipi.it/e/198

Abstract --------

We consider the combination of two approaches for the trace estimation of a symmetric matrix function f(A) when the only feasible operations are matrix-vector products and quadratic forms with f(A): stochastic estimators, such as the Hutchinson estimator and its refined variants Hutch++ and the recent XTrace, and probing methods based on graph colorings. Particularly effective is the case where we replace the indicator vectors for the coloring used in probing by random vectors whose non-zero entries have Rademacher distribution. A theoretical analysis exposes conditions under which using just one Rademacher probing vector per color is provably better than the classical probing approach. Numerical experiments show that existing methods are also outperformed under suitable conditions on the sparsity pattern of A and on the spectrum of f(A). This talk is based on a joint work with Andreas Frommer and Marcel Schweitzer.

-- Indico :: Email Notifier https://events.dm.unipi.it/e/198