Saved in:
| Main Authors: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2504.17899 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912346340851712 |
|---|---|
| author | Hecht, Michael Hofmann, Phil-Alexander Wicaksono, Damar Acosta, Uwe Hernandez Gonciarz, Krzysztof Kissinger, Jannik Sivkin, Vladimir Sbalzarini, Ivo F. |
| author_facet | Hecht, Michael Hofmann, Phil-Alexander Wicaksono, Damar Acosta, Uwe Hernandez Gonciarz, Krzysztof Kissinger, Jannik Sivkin, Vladimir Sbalzarini, Ivo F. |
| contents | We extend the univariate Newton interpolation algorithm to arbitrary spatial dimensions and for any choice of downward-closed polynomial space, while preserving its quadratic runtime and linear storage cost. The generalisation supports any choice of the provided notion of non-tensorial unisolvent interpolation nodes, whose number coincides with the dimension of the chosen-downward closed space. Specifically, we prove that by selecting Leja-ordered Chebyshev-Lobatto or Leja nodes, the optimal geometric approximation rates for a class of analytic functions -- termed Bos--Levenberg--Trefethen functions -- are achieved and extend to the derivatives of the interpolants. In particular, choosing Euclidean degree results in downward-closed spaces whose dimension only grows sub-exponentially with spatial dimension, while delivering approximation rates close to, or even matching those of the tensorial maximum-degree case, mitigating the curse of dimensionality. Several numerical experiments demonstrate the performance of the resulting multivariate Newton interpolation compared to state-of-the-art alternatives and validate our theoretical results. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_17899 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Multivariate Newton Interpolation in Downward Closed Spaces Reaches the Optimal Geometric Approximation Rates for Bos--Levenberg--Trefethen Functions Hecht, Michael Hofmann, Phil-Alexander Wicaksono, Damar Acosta, Uwe Hernandez Gonciarz, Krzysztof Kissinger, Jannik Sivkin, Vladimir Sbalzarini, Ivo F. Numerical Analysis We extend the univariate Newton interpolation algorithm to arbitrary spatial dimensions and for any choice of downward-closed polynomial space, while preserving its quadratic runtime and linear storage cost. The generalisation supports any choice of the provided notion of non-tensorial unisolvent interpolation nodes, whose number coincides with the dimension of the chosen-downward closed space. Specifically, we prove that by selecting Leja-ordered Chebyshev-Lobatto or Leja nodes, the optimal geometric approximation rates for a class of analytic functions -- termed Bos--Levenberg--Trefethen functions -- are achieved and extend to the derivatives of the interpolants. In particular, choosing Euclidean degree results in downward-closed spaces whose dimension only grows sub-exponentially with spatial dimension, while delivering approximation rates close to, or even matching those of the tensorial maximum-degree case, mitigating the curse of dimensionality. Several numerical experiments demonstrate the performance of the resulting multivariate Newton interpolation compared to state-of-the-art alternatives and validate our theoretical results. |
| title | Multivariate Newton Interpolation in Downward Closed Spaces Reaches the Optimal Geometric Approximation Rates for Bos--Levenberg--Trefethen Functions |
| topic | Numerical Analysis |
| url | https://arxiv.org/abs/2504.17899 |