Interpolation in Polynomial Spaces of p-Degree

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 ${\Pi }_{m,n,p}$. We show that the ${\Pi }_{m,n,p}$ choice compared to the tensor product spaces ${\Pi }_{m,n,\infty }$, reduces time complexity by a factor of ${\rho }_{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.

arXiv commentThe 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