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 O(|A|mn̄). Here, A is a downward closed set of cardinality $|A|$ equal to the dimension of the associated downward closed polynomial space ΠA, where 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 in non-tensorial Leja-ordered Chebyshev-Lobatto or Leja grids. To mitigate the curse of dimensionality, we utilize ᵖ-sets, with the l²-Euclidean case turning out to be the pivotal choice, leading to |A|/(n+1)ᵐ ∈ O(e⁻ᵐ). Expanding non-periodic functions, the FNT complements the approximation capabilities of the Fast Fourier Transform (FFT). Choosing ²-sets for A renders the FNT time complexity to be less than the FFT time complexity O((n+1)ᵐ m log(n)) in a range of n, behaving as O(eᵐ). Maintaining this advantage true for the differentials, the FNT sets a new standard in m-variate interpolation and approximation practice.