SubApSnap: Solving parameter-dependent linear systems with a snapshot and subsampling
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909826949316608 |
|---|---|
| author | Jones, Eleanor Nakatsukasa, Yuji |
| author_facet | Jones, Eleanor Nakatsukasa, Yuji |
| contents | A growing number of problems in computational mathematics can be reduced to the solution of many linear systems that are related, often depending smoothly or slowly on a parameter $p$, that is, $A(p)x(p)=b(p)$. We introduce an efficient algorithm for solving such parameter-dependent linear systems for many values of $p$. The algorithm, which we call SubApSnap (for \emph{Sub}sampled $A(p)$ times \emph{Snap}shot), is based on combining ideas from model order reduction and randomised linear algebra: namely, taking a snapshot matrix, and solving the resulting tall-skinny least-squares problems using a subsampling-based dimension-reduction approach. We show that SubApSnap is a strict generalisation of the popular DEIM algorithm in nonlinear model order reduction. SubApSnap is a sublinear-time algorithm, and once the snapshot and subsampling are determined, it solves $A(p_*)x(p_*)=b(p_*)$ for a new value of $p_*$ at a dramatically improved speed: it does not even need to read the whole matrix $A(p_*)$ to solve the linear system for a new value of $p_*$. We prove under natural assumptions that, given a good subsampling and snapshot, SubApSnap yields solutions with small residual for all parameter values of interest. We illustrate the efficiency and performance of the algorithm with problems arising in PDEs, model reduction, and kernel ridge regression, where SubApSnap achieves speedups of many orders of magnitude over a standard solution; for example over $20,000\times$ for a $10^7\times 10^7$ problem, while providing good accuracy. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_04825 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | SubApSnap: Solving parameter-dependent linear systems with a snapshot and subsampling Jones, Eleanor Nakatsukasa, Yuji Numerical Analysis 65F99, 65F20 A growing number of problems in computational mathematics can be reduced to the solution of many linear systems that are related, often depending smoothly or slowly on a parameter $p$, that is, $A(p)x(p)=b(p)$. We introduce an efficient algorithm for solving such parameter-dependent linear systems for many values of $p$. The algorithm, which we call SubApSnap (for \emph{Sub}sampled $A(p)$ times \emph{Snap}shot), is based on combining ideas from model order reduction and randomised linear algebra: namely, taking a snapshot matrix, and solving the resulting tall-skinny least-squares problems using a subsampling-based dimension-reduction approach. We show that SubApSnap is a strict generalisation of the popular DEIM algorithm in nonlinear model order reduction. SubApSnap is a sublinear-time algorithm, and once the snapshot and subsampling are determined, it solves $A(p_*)x(p_*)=b(p_*)$ for a new value of $p_*$ at a dramatically improved speed: it does not even need to read the whole matrix $A(p_*)$ to solve the linear system for a new value of $p_*$. We prove under natural assumptions that, given a good subsampling and snapshot, SubApSnap yields solutions with small residual for all parameter values of interest. We illustrate the efficiency and performance of the algorithm with problems arising in PDEs, model reduction, and kernel ridge regression, where SubApSnap achieves speedups of many orders of magnitude over a standard solution; for example over $20,000\times$ for a $10^7\times 10^7$ problem, while providing good accuracy. |
| title | SubApSnap: Solving parameter-dependent linear systems with a snapshot and subsampling |
| topic | Numerical Analysis 65F99, 65F20 |
| url | https://arxiv.org/abs/2510.04825 |