Phil-Alexander
Hofmann
/
Fast Newton Transform: Interpolation in Downward Closed Polynomial Spaces
Abstract.
The Fast Newton Transform (FNT) addresses the computational bottleneck that arises in solving high-dimensional problems such as 6d Boltzmann, Fokker-Planck, or Vlaslov equations, multi-body Hamiltonian systems, and the inference of governing equations in complex self-organizing systems. Specifically, the challenge lies in numerically computing function expansions and their derivatives fast, while achieving high approximation power. The FNT is a Newton interpolation algorithm with runtime complexity O(N n m), where N is the dimension of the downward closed polynomial space, n its degree and m the spatial dimension. We select subgrids from tensorial Leja-ordered Chebyshev-Lobatto grids based on downward closed sets. This significantly reduces the number of coefficients, N << (n+1)^m, while achieving optimal geometric approximation rates for a class of analytic functions known as Bos–Levenberg–Trefethen functions. Specifically, we investigate l^p-sets, where the Euclidean degree (p=2) turns out to be the pivotal choice for mitigating the curse of dimensionality. Furthermore, the differentiation matrices in Newton basis are sparse, enabling the implementation of fast pseudo-spectral methods on flat spaces, polygonal domains, and regular manifolds. Numerical experiments validate the algorithm's superior runtime performance over state-of-the-art approaches.