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.