cherubino

Calcolo della traccia di funzioni di matrici mediante stimatori stocastici e probing – Michele Rinelli (Scuola Normale Superiore)

Venue

Aula Seminari, Dipartimento di Matematica

Abstract

Le funzioni di matrici [1] sono un potente strumento dell’algebra lineare numerica per l’analisi di vari problemi provenienti dalle applicazioni. Tra gli esempi più noti vi sono l’inversa, per il ruolo nella risoluzione di sistemi lineari, e l’esponenziale, per il ruolo nelle equazioni differenziali. In altri casi è richiesto il calcolo della traccia tr(f(A)), dove f(A) è una generica funzione della matrice A. 

Cominciamo il seminario richiamando alcuni concetti di base sulle funzioni di matrici [1] per poi concentrarci sul calcolo della traccia. Esploriamo alcuni metodi stocastici, quali lo stimatore di Hutchinson, Hutch++ [2] e Xtrace [3], e i metodi probing [4] per il caso in cui A sia sparsa, basati sul calcolo di una d-colorazione del grafo associato ad A e che beneficiano delle proprietà di decadimento in f(A). In particolare, la recente combinazione tra Hutchinson e probing [5] mostra un miglior scaling dell’errore con la dimensione rispetto al probing deterministico e si rivela essere un approccio competitivo tra quelli nello stato dell’arte.

[1] N.J. Higham, Functions of Matrices: Theory and Computation, Society for Industrial and Applied Mathematics, Philadelphia, USA, 2008.
[2] R. A. Meyer, C. Musco, Ch. Musco, and D. P. Woodruff, Hutch++: Optimal stochastic trace estimation, Symposium on Simplicity in Algorithms (SOSA), SIAM, 2021, pp. 142–155.
[3] E. N. Epperly, J. A. Tropp, and R. J. Webber, Xtrace: Making the most of every sample in stochastic trace estimation, arXiv preprint arXiv:2301.07825 [math.NA], 2023.
[4] A. Frommer, C. Schimmel, M. Schweitzer: Analysis of probing techniques for sparse approximation and trace estimation of decaying matrix functions. SIAM J. Matrix Anal. Appl. 42(3), 1290–1318, 2021.
[5] A. Frommer, M. Rinelli, and M. Schweitzer. Analysis of stochastic probing methods for estimating the trace of functions of sparse symmetric matrices, arXiv preprint arXiv:2308.07722 [math.NA], 2023.

Torna in cima