I am a scientific researcher and software developer.

‹ Speaker Engagements
Icon

Fast Newton Transform: Interpolation in Downward Closed Polynomial Spaces


    • Date: 2025-07-30  
    • Location: Montreal, Canada  
    • Institution: SIAM AN 25  

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(Nnm)O(Nnm), where N is the dimension of the downward closed polynomial space, nn its degree and mm 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)mN \ll (n+1)^m, while achieving optimal geometric approximation rates for a class of analytic functions known as Bos–Levenberg–Trefethen functions. Specifically, we investigate p\ell^p-multi-index sets, where the Euclidean degree (p=2p=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.