Seminar on Numerical Analysis

Solving a sequence of eigenvalue problems using snapshot and row subsampling

by Francesco Hrobat (University of Oxford, St. Catherine's College)

→ Europe/Rome
Sala Riunioni (Dipartimento di Matematica)

Sala Riunioni

Dipartimento di Matematica

Largo Bruno Pontecorvo, 5, 56127 Pisa
Description

A sequence of eigenvalue problems requires solving $A_i\vec{x}_i = \lambda_i\vec{x}_i$ for $i = 1, \dots, N$, $N \gg 1$, where $\lambda_i$ is typically the largest or smallest eigenvalue of $A_i$. Often $A_i = A(p_i)$ comes from a smooth map $p \rightarrow A(p) \in \mathbb{C}^{n \times n}$, so the matrices change gradually along the sequence. Under this assumption, we introduce an efficient algorithm combining reduced order modeling and row subsampling, as done in [E. Jones and Y. Nakatsukasa, 2025] for linear systems. A set of $r \ll N$ snapshot points yields an orthonormal basis $Q \in \mathbb{C}^{n \times r}$, and each $\vec{x}_i$ is sought in $\operatorname{span}(Q)$. Instead of the classic Rayleigh-Ritz projection $Q^*A(p_i)Q$, we access only a few selected rows of $A(p_i)$, as in sketched Rayleigh-Ritz [Y. Nakatsukasa and J. A. Tropp, 2024]; this matters when entries of $A(p)$ are expensive to compute. Unlike for linear systems, the same rows work well for every $p$, as long as the snapshots are unchanged. We also propose an update strategy for the snapshot matrix. Our analysis, generalizing [M. Guido, D. Kressner, and P. Ricci, 2024], bounds the eigenvector error at unseen parameter values: if $A(p)$ admits an analytic extension, convergence is asymptotically exponential in the number of snapshots, regardless of their distribution. We extend the method to singular value and generalized eigenvalue problems, and present numerical results demonstrating its efficiency.

Organised by

Fabio Durastante, Leonardo Robol