Paperlane

no. 6 · Monday 2 November 2026

Interpolation in Polynomial Spaces of p-Degree

Phil-Alexander Hofmann, Damar Wicaksono and Michael Hecht

math.NA · v5

Abstract

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.

comments
The work on which this manuscript is based has undergone substantial revisions that significantly change the underlying formulation. Consequently, the analysis presented here is no longer applicable to the revised work and has become obsolete
fields
Numerical Analysis
pdf ↗ page arXiv:2507.13640 ↗