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.
Categories: math.NA cs.NA