标题： 多项式空间中的插值 显示英文标题

标题： Interpolation in Polynomial Spaces of p-Degree

摘要： 我们最近引入了快速牛顿变换（FNT），这是一种在空间维数为$m$的下闭多项式空间中执行多变量牛顿插值的算法。 在本工作中，我们分析了 FNT 在特定的一类下闭集合$A_{m,n,p}$的上下文中，这些集合定义为所有满足$\ell^p$范数小于$n$的多指标，其中$p \in [0,\infty]$。 这些集合诱导出下闭多项式空间$\Pi_{m,n,p}$，在该空间中，FNT 算法的时间复杂度为 $\mathcal{O}(|A_{m,n,p}|mn)$。 我们证明，在这种设置下，与张量积空间相比，复杂度提高了$\rho_{m,n,p}$倍，当$m \lesssim n^p$增加时，这种改进以超指数方式衰减。 此外，我们展示了 FNT 所采用的分层方案的构造，并展示了其在敏感性分析中计算活动分数的性能。 显示英文摘要

摘要： We recently introduced the Fast Newton Transform (FNT), an algorithm for performing multivariate Newton interpolation in downward closed polynomial spaces of spatial dimension $m$. In this work, 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]$. These sets induce the downward closed polynomial space $\Pi_{m,n,p}$, within which the FNT algorithm achieves a time complexity of $\mathcal{O}(|A_{m,n,p}|mn)$. We show that this setting, compared to tensor product spaces, yields an improvement in complexity by a factor $\rho_{m,n,p}$, which decays super exponentially with increasing spatial dimension when $m \lesssim n^p$. Additionally, we demonstrate the construction of the hierarchical scheme employed by the FNT and showcase its performance to compute activity scores in sensitivity analysis.