The Fast Newton Transform: Interpolation in Downward Closed Polynomial Spaces

We present the Fast Newton Transform (FNT), an algorithm for performing $m$-variate Newton interpolation in downward closed polynomial spaces with time complexity $\mathcal{O}(\mathrm{\mid }A\mathrm{\mid }m\bar{n})$. Here, $A$ is a downward closed set of cardinality $\mathrm{\mid }A\mathrm{\mid }$ equal to the dimension of the associated downward closed polynomial space ${\mathrm{\Pi }}_A$, where $\bar{n}$ denotes the mean of the maximum polynomial degrees across the spatial dimensions $m$. For functions being analytic in an open Bernstein poly-ellipse, geometric approximation rates apply, when interpolating with respect to ${\mathrm{\ell }}^p$-sets $A_{m,n,p}$, in non-tensorial Leja ordered Chebyshev-Lobatto or Leja grids. Especially, the ${\mathrm{\ell }}^2$-Euclidean case $A_{m,n,2}$ turns out to be the pivotal choice to mitigate the curse of dimensionality, leading to a ratio $\mathrm{\mid }{A}_{m,n,2}\mathrm{\mid }\mathrm{/}\mathrm{\mid }{A}_{m,n,\mathrm{\infty }}\mathrm{\mid }$ that decays exponentially with spatial dimension $m$, while reaching close to or the same approximation power as the tensorial ${\mathrm{\ell }}^{\mathrm{\infty }}$-case. Expanding non-periodic functions, the FNT complements the approximation capabilities of the Fast Fourier Transform (FFT), whereas the choice of ${\mathrm{\ell }}^p$-sets renders the FNT time complexity to be less than the FFT time complexity in a wide range of $n$, that exponentially increases with $m$. Maintaining this advantage true for the differentials, the FNT sets a new standard in $m$-variate interpolation and approximation practice.