Fast Multivariate Newton Interpolation for Downward Closed Polynomial Spaces and Applications to Numerical Differential Geometry
Michael Hecht (CASUS - Center for Advanced Systems Understanding Helmholtz-Zentrum Dresden-Rossendorf e.V. (HZDR), Görlitz & Mathematical Institute, University Wrocław, Poland), Phil-Alexander Hofmann, Damar Wicaksono, and Michael Hecht
We introduce a fast Newton interpolation algorithm with a runtime complexity of \(\mathcal{O}(Nn)\), where \(N\) denotes the dimension of the underlying downward closed polynomial space and \(n\) its \(l_p\)-degree, where \(p > 1\). We demonstrate that the algorithm achieves the optimal geometric approximation rate for analytic Bos-Levenberg-Trefethen functions in the hypercube. In this case, the Euclidean degree (\(p = 2\)) emerges as the pivotal choice for mitigating the curse of dimensionality. The spectral differentiation matrices in the Newton basis are sparse, enabling the implementation of fast pseudo-spectral methods on flat spaces, polygonal domains, and regular manifolds.
In particular, we revisit our former contribution, entitled Global Polynomial Level Sets (GPLS) for Numerical Differential Geometry of Smooth Closed Surfaces.
The GPLS approximates a broad class of smooth surfaces being only sampled as point clouds by a global polynomial level set, enabling posterior efficient and accurate computation of differential-geometric quantities like mean and Gauss curvature or even 4\(^{\text{th}}\)-order terms such as the Laplacian of mean curvature. The GPLS significantly reduces the number of surface points required compared to classic alternatives that rely on surface meshes or embedding grids. We sketch extensions to higher dimensions and discuss applications in numerical differential geometry.