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

标题： Interpolation in Polynomial Spaces of p-Degree

摘要： 我们最近引入了快速牛顿变换（FNT），这是一种分层算法，用于在任意向下闭合的多项式空间中进行多变量牛顿插值，该空间的空间维数为$m$。 在此，我们分析了 FNT 在特定的向下闭合集$A_{m,n,p}$的上下文中，该集定义为所有满足$\ell^p$范数小于$n$的多重指标，其中$p \in [0,\infty]$。 FNT 在所诱导的向下闭合多项式空间$\Pi_{m,n,p}$上的时间复杂度为$\mathcal{O}(|A_{m,n,p}|mn)$。 我们证明，与张量积空间 $\Pi_{m,n,\infty}$相比， $\Pi_{m,n,p}$的选择将时间复杂度降低了 $\rho_{m,n,p}$倍，在 $m \lesssim n^p$时随着空间维度呈超指数级衰减。我们展示了 FNT 的效率，通过在敏感性分析中计算活动得分来说明。 显示英文摘要

摘要： 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.