Mathematical Foundations of Complex System Science
High-Dimensional Interpolation and Fast Spectral Methods
Research
Polynomial interpolation goes back to Newton, Lagrange, and others, and its fundamental importance in mathematics and computing is undisputed. We have extended Newton and Lagrange interpolation to a multivariate interpolation algorithm (MIP), maintaining their numerical stability and computational efficiency.
Currently, we aim to realise a fast Newton interpolation algorithm (FNP) of runtime complexity O(Nn), where N denotes the dimension of the underlying downward closed polynomial space and n its lp-degree, p >1. MIP and FNP reach the optimal geometric approximation rate for analytic Bos-Levenberg-Trefethen functions in the hypercube, in which case the Euclidean degree, p=2, turns out to be the pivotal choice for resisting the curse of dimensionality, Fig.1.
The spectral differentiation matrices in Newton basis are sparse, which enables realizing fast pseudo-spectral methods on flat spaces, polygonal domains, and regular manifolds., Fig2.
Papers:
Hecht, M., and Sbalzarini, I.F. Fast interpolation and Fourier transform in high-dimensional spaces. In Intelligent Computing. Proc. 2018 IEEE Computing Conf., Vol.2, (London, UK), K. Arai, S. Kapoor, and R. Bhatia, Eds., vol. 857 of Advances in Intelligent Systems and Comput- ing, Springer Nature, pp. 53–75, 2018.
Hecht, M., Gonciarz, K., Michelfeit, J., Sivkin, V., and Sbalzarini, I.F. Multivariate Interpolation in Unisolvent Nodes–Lifting the Curse of Dimensionality, arXiv:2010.10824, 2020.
Hecht, M., Hoffmann, K.B., Cheeseman, B.L., and Sbalzarini, I.F. Multivariate Newton interpolation. arXiv:1812.04256, 2018.
Hecht, M., Hoffmann, K.B., Cheeseman, B.L., and Sbalzarini, I.F. A Quadratic-Time Algorithm for General Multivariate Polynomial Interpolation. arXiv:1710.10846 2018.