Interpolation in Polynomial Spaces of p-Degree
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911092822769664 |
|---|---|
| author | Hofmann, Phil-Alexander Wicaksono, Damar Hecht, Michael |
| author_facet | Hofmann, Phil-Alexander Wicaksono, Damar Hecht, Michael |
| contents | We recently introduced the Fast Newton Transform (FNT), an hierarchical algorithm for performing multivariate Newton interpolation in arbitrary downward closed polynomial spaces of spatial dimension $m$. Here, we analyze the FNT in the context of a specific family of downward closed sets $A_{m,n,p}$, defined as all multi-indices with $\ell^p$ norm less than $n$ with $p \in [0,\infty]$. The FNT performs with time complexity $\mathcal{O}(|A_{m,n,p}|mn)$ on the induced downward closed polynomial spaces $Π_{m,n,p}$. We show that the $Π_{m,n,p}$ choice compared to the tensor product spaces $Π_{m,n,\infty}$, reduces time complexity by a factor of $ρ_{m,n,p}$, decaying super exponentially with spatial dimension when $m \lesssim n^p$. We showcase the efficiency of the FNT by computing activity scores in sensitivity analysis. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_13640 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Interpolation in Polynomial Spaces of p-Degree Hofmann, Phil-Alexander Wicaksono, Damar Hecht, Michael Numerical Analysis 65D15 We recently introduced the Fast Newton Transform (FNT), an hierarchical algorithm for performing multivariate Newton interpolation in arbitrary downward closed polynomial spaces of spatial dimension $m$. Here, we analyze the FNT in the context of a specific family of downward closed sets $A_{m,n,p}$, defined as all multi-indices with $\ell^p$ norm less than $n$ with $p \in [0,\infty]$. The FNT performs with time complexity $\mathcal{O}(|A_{m,n,p}|mn)$ on the induced downward closed polynomial spaces $Π_{m,n,p}$. We show that the $Π_{m,n,p}$ choice compared to the tensor product spaces $Π_{m,n,\infty}$, reduces time complexity by a factor of $ρ_{m,n,p}$, decaying super exponentially with spatial dimension when $m \lesssim n^p$. We showcase the efficiency of the FNT by computing activity scores in sensitivity analysis. |
| title | Interpolation in Polynomial Spaces of p-Degree |
| topic | Numerical Analysis 65D15 |
| url | https://arxiv.org/abs/2507.13640 |