SCS: Michael Hecht (CASUS / HZDR & University Wroclaw)

Tuesday Nov 19, 2024, 10:00 AM → 11:00 AM America/New_York

3rd floor classroom (162)

The Fast Newton Transform: Interpolation in downward closed spaces reaching optimal geometric approximation rates for Bos-Levenberg-Trefethen functions

We address the computational bottleneck that arises in solving high-dimensional problems such as 6D Fokker-Planck 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.

We present the Fast Newton Transform (FNT), a novel algorithm for multivariate polynomial interpolation with a runtime of nearly Nlog(n), where N scales only sub-exponentially with spatial dimension, surpassing the runtime of the tensorial Fast Fourier Transform (FFT). This establishes the FNT as a new standard in spectral methods, particularly suitable for high-dimensional, non-periodic PDE problems, and interpolation tasks.

We prove the optimal geometric approximation rates for a class of analytic functions—termed Bos–Levenberg–Trefethen functions—to be reached by the FNT and to be maintained for the derivatives of the interpolants. We empirically demonstrate the FNT’s superiority in runtime, compared to state-of-the-art alternatives, and discuss extensions to other, non-polynomial, function spaces and non-flat domains. 

Joint work of Phil-Alexander Hofmann, Damar Wicaksono,  Gentian Zavalani, and  Michael Hecht