PYSANUM

Previous seminars

Anno 2024/25

14.30 – 10 ottobre 2024
Lorenzo Lazzarino (University of Oxford)

Aula Riunioni, Dipartimento di Matematica
Sull’estrazione di valori singolari accurati da sottospazi approssimati

Abstract

La decomposizione ai valori singolari (SVD) è uno strumento fondamentale dell’algebra lineare numerica, ma per matrici di enormi dimensioni il suo costo computazionale è proibitivo. L’approssimazione dei valori singolari è quindi cruciale in vari campi della matematica, dell’ingegneria e data science. Questa operazione è spesso parte di processi più ampi nei quali è possibile ottenere un’approssimazione dei sottospazi singolari tramite metodi come la bi-diagonalizzazione di Golub-Kahan, iterazioni sui sottospazi o tecniche randomizzate.

In questa presentazione introdurremo strumenti per estrarre valori singolari da approssimazioni ortonormali di sottospazi singolari, esaminando tecniche classiche come Rayleigh-Ritz e la proiezione SVD (su un lato), confrontandole con approcci più recenti come la SVD randomizzata (HMT) e il metodo di Nyström generalizzato (GN), che forniscono approssimazioni sorprendentemente significamente più accurate. Includeremo la necessaria introduzione alle approssimazioni di basso rango, un altro grande problema legato alla SVD, e alla randomizzazione, tecnica di grande impatto nell’algebra lineare numerica.

Analizzeremo infine l’accuratezza di queste tecniche utilizzando la teoria delle perturbazioni di matrice, per confrontare i vari metodi e giustificare le osservazioni dedotte da esperimenti numerici.

14.30 – 21 ottobre 2024
Lorenzo Piccinini (Università di Bologna)

Aula Seminari, Dipartimento di Matematica
LSQR troncato per problemi ai minimi quadrati matriciali e tensoriali

Abstract

Siamo interessati alla soluzione numerica del problema ai minimi quadrati sia in forma matriciale $$\min\limits_{X \in \mathbb{R}^{m \times m}} \Vert C_1C_2^T \, – \, A_1XB_1 \, – \, A_2XB_2\Vert_F$$ sia in forma tensoriale $$\min\limits_{X \in \mathbb{R}^{m \times m\times \ldots \times m}} \Vert \mathcal{D} \,- \sum\limits_{i=1}^p \mathcal{X} \times_1 A^{(i)} \times_2 B^{(i)} \times_3 C^{(i)}\Vert_F$$ dove $C = C_1C_2^T$ e $\mathcal{D}$ hanno rango basso. Per chiarezza ci concentreremo sul caso p = 2,3, osservando che la generalizzazione a un numero maggiore di termini avviene in maniera naturale. Ci concentreremo inizialmente sulla derivazione dell’algoritmo LSQR in forma matriciale e tensoriale. Successivamente, deriveremo le rispettive versioni troncate, mostrando come, nei casi in cui la soluzione abbia basso rango, il troncamento influenzi l’algoritmo. Nel caso matriciale è particolarmente interessante il confronto con il metodo dei Gradienti Coniugati (CG), già studiato nella sua versione matriciale e troncata. Sempre nel caso matriciale, mostreremo un’applicazione al problema del Dictionary Learning. Per il caso tensoriale, mostreremo un’applicazione per la soluzione numerica di PDE.

Anno 2023/24

14:30 – 17 ottobre 2023

Alberto Bucci (Università di Pisa)

Nikita Deniskin (Scuola Normale Superiore)

Igor Simunec (Scuola Normale Superiore)

Aula Magna, Dipartimento di Matematica

Presentazione seminari PYSANUM

Abstract

In questo primo incontro presenteremo PYSANUM. Primo ciclo di seminari di analisi numerica rivolto agli studenti!

16.00 – 25 ottobre 2023
Chiara Faccio (Scuola Normale Superiore)

Aula Riunioni, Dipartimento di Matematica
Caratterizzazione strutturale dell’acqua liquida: un approccio computazionale basato sulla teoria dei grafi

Abstract

L’acqua liquida, oltre ad essere fondamentale per la vita sulla Terra, ha da lungo tempo affascinato gli scienziati a causa di diverse anomalie. Nel corso degli anni sono state avanzate diverse ipotesi per spiegare queste particolarità. La più accreditata prevede la presenza nella regione super-raffreddata di due fasi a densità diverse: la fase liquida a bassa densità (LDL) e la fase liquida ad alta densità (HDL). Nel nostro lavoro [1], abbiamo dimostrato che è possibile identificare queste due forme nelle reti d’acqua attraverso un approccio computazionale basato sulle simulazioni di dinamica molecolare e sul calcolo della Comunicabilità Totale (Total Communicability) del grafo associato [2], dove i nodi rappresentano le molecole d’acqua e gli archi le connessioni (interazioni) tra di esse. In un lavoro successivo [3], abbiamo approfondito l’applicazione della teoria delle reti, esaminando varie misure di connettività, centralità e metriche globali, con l’obiettivo di fornire una caratterizzazione topologica e geometrica dell’acqua liquida.

Lavoro congiunto con Michele Benzi (Scuola Normale Superiore), Isabella Daidone (Dipartimento di Scienze Fisiche e Chimiche, Università dell’Aquila) e Laura Zanetti-Polzi (Centro S3, Istituto di Nanoscienze del CNR, Modena)

[1] C. Faccio, M. Benzi, L. Zanetti-Polzi, & I. Daidone, Low-and high-density forms of liquid water revealed by a new medium-range order descriptor. Journal of Molecular Liquids, 355, 118922, 2022.
[2] M. Benzi, & C. Klymko, Total communicability as a centrality measure. Journal of Complex Networks, 1(2), 124-149, 2013.
[3] M. Benzi, I. Daidone, C. Faccio, and L. Zanetti-Polzi. ‘Structural analysis of water networks’. Journal of Complex Networks, 11(1):cnad001, 01 2023.

16.00 – 14 novembre 2023
Michele Rinelli (Scuola Normale Superiore)

Aula Seminari, Dipartimento di Matematica
Calcolo della traccia di funzioni di matrici mediante stimatori stocastici e probing

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.

16.00 – 27 novembre 2023
Martina Iannacito (KU Leuven)

Aula Riunioni, Dipartimento di Matematica
Introduzione ai tensori: dalle applicazioni alle sfide contemporanee

Abstract

Per oltre un secolo, i matematici sono stati affascinati dallo studio delle proprietà di famiglie di matrici. Gli oggetti con cui allora iniziarono a confrontarsi sono oggi noti come tensori o array multidirezionali. Lo studio dei tensori ha acquisito particolare rilevanza grazie alle molteplici applicazioni in cui forniscono importanti benefici. Queste strutture matematiche multidimensionali garantiscono l’unicità della fattorizzazione (sotto ipotesi non eccessivamente complesse), consentono rappresentazioni più adatte di fenomeni complessi e delle loro intricate interazioni. Infine, se rappresentati in modo ottimale, i tensori offrono vantaggi computazionali. Tutte queste loro proprietà hanno aperto diverse nuove direzioni di ricerca in campo matematico, numerico e computazionale.
Nella prima metà di questa presentazione, esamineremo problemi provenienti da applicazioni concrete in cui i tensori sono stati di innovazione. Contemporaneamente, verrà fornita una panoramica di alcune tecniche di decomposizione tensoriale che meglio si adattano al problema considerato di volta in volta.
Il focus della seconda parte si sposterà sulle sfide contemporanee incontrate nello sviluppo di tecniche basate su array multidimensionali, e nell’implementazione di nuovi algoritmi per la fattorizzazione tensoriale. Questa discussione offrirà spunti di riflessione sul panorama in evoluzione della ricerca sui tensori, evidenziandone la rilevanza e il potenziale.

16.00 – 12 dicembre 2023
Alessandro Filippo (Università di Roma Tor Vergata)

Aula Seminari, Dipartimento di Matematica
Reti complesse: Robustezza, indici di centralità e nuove strategie per il ranking dei nodi

Abstract

Determinare quali siano i nodi più importanti in una rete complessa è uno dei problemi principali dell’analisi delle reti. Tale problema, anche noto come il problema del ranking, viene tipicamente risolto attraverso il calcolo delle misure di centralità.

Tuttavia, cambiamenti strutturali improvvisi, quali la rimozione di alcuni nodi o archi, possono invalidare la nostra conoscenza dei nodi più critici. Per esempio, nodi dapprima cruciali potrebbero perdere tutta la loro importanza qualora rimanessero isolati.
Quindi, per studiare l’impatto della rimozione dei nodi più influenti da una rete, sarebbe necessario ricalcolare costantemente le misure di centralità, un’operazione spesso impraticabile per reti di grandi dimensioni. Al contrario, evitare del tutto il ricalcolo potrebbe fornire una rappresentazione della realtà poco accurata.

In questo talk illustrerò due nuove strategie per ridurre il costo computazionale del calcolo sequenziale delle centralità, fornendo giustificazioni teoriche a supporto. Infine, mostrerò come sia possibile impiegare queste strategie per valutare la robustezza di una rete ad attacchi mirati.

Tratto da un lavoro in collaborazione con Daniele Bertaccini.

D. Bertaccini, A. Filippo. A proposal for ranking through selective computation of centrality measures. PLOS ONE, 18, 2023.

14.30 – 12 febbraio 2024
Miryam Gnazzo (Gran Sasso Science Institute)

Aula Seminari, Dipartimento di Matematica
Un oracolo per la risoluzione di problemi di matrix nearness

Abstract

Data una matrice A, un problema di matrix nearness consiste nel trovare la matrice più vicina ad A all’interno di un insieme specifico di matrici, misurando la distanza in una norma matriciale. Ad esempio trovare la matrice singolare più vicina data una matrice invertibile rientra in questa classe di problemi. In alcuni casi può essere utile estendere questa classe di problemi, considerando polinomi di matrici, cioè polinomi i cui coefficienti sono matrici.

Nella prima parte di questa presentazione, ci sarà un’introduzione ai problemi di matrix nearness e alla loro estensione ai polinomi di matrici, con alcuni esempi di applicazioni. Nella seconda parte, invece, scenderemo nei dettagli, descrivendo come poter interpretare i problemi di matrix nearness come problemi di ottimizzazione su un opportuno insieme di matrici. Infine presenterò un nuovo approccio che utilizza un oracolo per ottenere informazioni sulla soluzione del problema di matrix nearness.

Lavoro congiunto con Vanni Noferini (Aalto University), Lauri Nyman (Aalto University) e Federico Poloni (Università di Pisa).

[1] M. Gnazzo, V. Noferini, L. Nyman, F. Poloni. The Oracle of Breselenz: a general-purpose Riemannian optimizer to solve nearness problems in matrix theory, in preparation (2024).

16.00 – 21 marzo 2024
Francesco Hrobat (Scuola Normale Superiore)

Aula Seminari, Dipartimento di Matematica
Calcolo della SVD tramite funzioni di Zolotarev

Abstract

In questo seminario verranno presentati due algoritmi recenti (ZOLO-PD e QDWH) che forniscono la base per nuovi algoritmi paralleli per il calcolo della SVD e della decomposizione agli autovalori simmetrica.

Gli algoritmi presi in esame si basano sul calcolo della decomposizione polare di una matrice, la quale viene costruita tramite la funzione segno di una matrice. La funzione segno matriciale può essere a sua volta calcolata con elevata precisione attraverso approssimazioni razionali su intervalli simmetrici reali della stessa funzione segno. Ciò conduce naturalmente alla teoria dell’approssimazione e, in parte, alla teoria delle funzioni ellittiche. Lo studio dettagliato dell’approssimazione razionale ottimale della funzione segno è stato condotto da Zolotarev, focalizzandosi in particolare su due problemi, noti oggi come terzo e quarto problema di Zolotarev.

14.30 – 12 aprile 2024
Ivan Bioli (Università degli Studi di Pavia)

Aula Riunioni, Dipartimento di Matematica
Introduzione all’ottimizzazione Riemanniana e applicazioni a equazioni matriciali

Abstract

Dato il problema di minimizzazione di una funzione costo f su una varietà Riemanniana immersa M, l’ottimizzazione Riemanniana offre un’alternativa al tradizionale approccio di trattare il problema come un’ottimizzazione Euclidea vincolata, generalizzando gli algoritmi di ottimizzazione Euclidea non vincolata per operare direttamente sullo spazio ambiente curvo M.

Nella prima parte di questo seminario, esamineremo i concetti fondamentali della geometria differenziale e Riemanniana, rivolgendoci anche a un pubblico non ancora familiare con tali argomenti. Successivamente, approfondiremo come l’algoritmo di discesa del gradiente possa essere esteso alla sua versione Riemanniana. Infine, esploreremo applicazioni pratiche. Come primo esempio didattico, discuteremo il calcolo degli autovalori estremi di una matrice simmetrica tramite la minimizzazione del quoziente di Rayleigh. Successivamente, illustreremo come per la risoluzione di equazioni matriciali lineari l’ottimizzazione Riemanniana si dimostri competitiva con gli algoritmi stato dell’arte.

Per approfondimenti teorici sull’argomento, consigliamo l’eccellente libro di N. Boumal [2]. Per iniziare a sperimentare gli algoritmi di ottimizzazione Riemanniana, raccomandiamo la toolbox Manopt [1].

References:
[1] Nicolas Boumal et al. “Manopt, a Matlab Toolbox for Optimization on Manifolds”. In:
Journal of Machine Learning Research 15.42 (2014), pp. 1455–1459.
[2] Nicolas Boumal. An introduction to optimization on smooth manifolds. Cambridge
University Press, 2023.

14.30 – 29 aprile 2024
Umberto Zerbinati (University of Oxford)

Aula Riunioni, Dipartimento di Matematica
Quasi-ottimalità del metodo agli elementi finiti per l’equazione di Helmholtz

Abstract

Per iniziare discuteremo come la quasi-ottimalità del metodo agli elementi finiti per il problema di Helmholtz dipende dalla taglia degli elementi della mesh e dal numero d’onda. In particolare, mostreremo l’argomentazione di Schatz per garantire la quasi-ottimalità del metodo di Galerkin. Proporremo poi un criterio alternativo basato sulla T-coercività e T-coercività debole che metta in risalto la relazione tra la taglia della mesh e la distanza del numero d’onda dagli autovalori del Laplaciano. Infine proporremo un metodo adattativo per costruire un mesh, ottima rispetto al numero di gradi di libertà, sulla quale è garantita la quasi ottimalità degli elementi finiti.

14.30 – 6 maggio 2024
Elia Onofri (Istituto per le Applicazioni del Calcolo – CNR)

Aula Seminari, Dipartimento di Matematica
Managing Pedestrian Flows in Crowded Museums

Abstract

In this talk, we present an all-around study of the visitors’ flow in crowded museums: a combination of Lagrangian field measurements and statistical analyses enables us to create stochastic digital-twins of the guest dynamics, unlocking comfort- and safety-driven optimisations. Specifically, we employ a Lagrangian IoT-based visitor tracking system relying on Raspberry Pi receivers, displaced in fixed positions throughout the museum rooms, and on portable Bluetooth Low-Energy (BLE) beacons handed over to the visitors. The signal intensity provides a proxy for the distance to the antennas and thus indicative positioning. However, RSSi signals are well-known to be noisy, even in ideal conditions (high antenna density, absence of obstacles, absence of crowd, etc.). We present a cascaded AI-classifier method to perform accurate RSSi-based visitor tracking when the density of antennas is relatively low allowing us to reconstruct visitor trajectories at room-scale thanks to a convenient encoding of the museum topology in terms of a total-coloured graph. Via a clustering analysis, hinged on an original Wasserstein-like trajectory-space metric, we analyse the visitors’ paths to get behavioural insights, including the most common flow patterns. On these bases, we build the transition matrix describing, in probability, the room-scale visitor flows. Such a matrix is the cornerstone of a stochastic model capable of generating visitor trajectories in silico. We conclude by employing the simulator to enhance the museum’s fruition while respecting numerous logistic and safety constraints. This is possible thanks to optimised ticketing and new entrance/exit management. Our case study are the Galleria Borghese Museum in Rome and the Peggy Guggenheim Foundation in Venice (Italy), in which we performed multiple real-life data acquisition campaigns.

References
[1] Pietro Centorrino, Alessandro Corbetta, Emiliano Cristiani, and Elia Onofri. Measurement and analysis of visitors’ trajectories in crowded museums. In IMEKO TC-4, pages 423–428, Florence, Italy, 12 2019. International Conference on Metrology for Archaeology and Cultural Heritage. imeko:2019-83.
[2] Pietro Centorrino, Alessandro Corbetta, Emiliano Cristiani, and Elia Onofri. Managing crowded museums: visitors flow measurement, analysis, modeling, and optimization. Journal of Computational Science, 53:1– 17, 04 2021. doi:10.1016/j.jocs.2021.101357.
[3] Elia Onofri and Alessandro Corbetta. RSSi-based visitor tracking in museums via cascaded AI classifiers and coloured graph representations. Collective Dynamics, 6:1—17, 01 2022. doi:10.17815/CD.2021.131.
[4] Pietro Centorrino, Emiliano Cristiani, Pietro Ferrara, Danilo Macchion, and Elia Onofri. Measurement and analysis of the visitors behavior in the Peggy Guggenheim collection. Technical report, IAC–CNR, 2 2023.

16.00 – 22 maggio 2024
Stefano Sicilia (Gran Sasso Science Institute)

Aula Riunioni, Dipartimento di Matematica
Stabilization of a Matrix Via a Low Rank-Adaptive Matrix ODE

Abstract

Let A be a square matrix with a given structure (e.g. real matrix, sparsity pattern, Toeplitz structure, etc.) and assume that it is unstable, i.e. at least one of its eigenvalues lies in the complex right half-plane. The problem of stabilizing A consists in the computation of a matrix B, whose eigenvalues have negative real part and such that the perturbation Δ = B − A has minimal norm. The structured stabilization further requires that the perturbation preserves the structural pattern of A. We solve this non-convex problem by a two-level procedure which involves the computation of the stationary points of a matrix ODE. We exploit the low rank underlying features of the problem by using an adaptive-rank integrator that follows slavishly the rank of the solution. We show the benefits derived from the low rank setting in several numerical examples, which also allow to deal with high dimensional problems.

14.30 – 12 giugno 2024
Taejun Park (University of Oxford)

Aula Riunioni, Dipartimento di Matematica
Accuracy and stability of randomized low-rank approximations

Abstract

Randomization in numerical linear algebra (NLA) is a powerful technique for reducing the complexity of many NLA algorithms. In this talk, we discuss three popular (randomized) methods for computing low-rank approximations of matrices: randomized SVD, the (generalized) Nyström method and the CUR decomposition. We provide an overview of each method and study their accuracy and stability.