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