Title: Fast Spectral Methods for High Dimensional Spaces and Regular Manifolds

Research Area: Mathematical Foundations and Statistical Learning

The beauty and fascinating enigmatic nature that complex systems embody might be the driving force behind the ambitions of many scientists in their realm of scientific research. As I have experienced in my interdisciplinary exchange with scientists across the world, resolving the computational bottleneck of scientific questions being addressed today often turns out to be the central issue.

This bottleneck arises from accurately and efficiently expanding function data into closed-form expressions to solve general PDE problems. While there is a widespread belief in the infeasibility of polynomial interpolation for tackling this task, I quote Prof. Lloyd N. Trefethen, addressing this misconception:

…“one can show that interpolation by polynomials in Chebyshev points is equivalent to interpolation of periodic functions by series of sines and cosines in equispaced points. The latter is the subject of discrete Fourier analysis, and one cannot help noting that whereas there is widespread suspicion that it is not safe to compute with polynomials, nobody worries about the Fast Fourier Transform (FFT)! In the end, that this may be the biggest difference between Fourier and polynomial interpolants, the difference in their reputations.” (Trefethen, L.N. (2019), Approximation theory and approximation practice, Volume 164 SIAM. )

I suggest continuing the endeavour of transplanting FFT-based methods to non-periodic functions by exploiting multivariate polynomial interpolation techniques that resist the curse of dimensionality. Our strategies suggest the implementation of a new generation of fast spectral methods that extend the applicability of FFT-based ones to non-periodic problems and turn out to be superior in runtime to FFT-based pseudo-spectral methods in high dimensions dim =2, …6,7. 

Aims

In 2000 the SIAM Guest-Editors Jack Don-Garra and Francis Sullivan put together a list they call the “Top Ten Algorithms of the Century.” (Dongarra, J. and F.Sullivan (2000). Top ten algorithms of the century. Computing in Science and Engineering)

It is no surprise that two  algorithms of that prominent list are the heart of fast (pseudo) spectral methods: The Fast Fourier Transfrom (FFT) and the Fast Multipole Methods (FMMs).  The article closes by: 

“What new insights and algorithms will the 21st century bring? The complete answer obviously won’t be known for another hundred years. One thing seems certain, however”…”The new century is not going to be very restful for us, but it is not going to be dull either!”

We focus on extending the applicability of fast spectral methods, by not only addressing existing limitations such as the need for periodicity in FFTs or the quadratic decay of the Coulomb field in FMMs, but by extending them to high dimensions, while maintaining their efficiency, avoiding exponential growth of the runtime and storage complexity. Two of our own results make this endeavor complementing recent contributions in the field: 

• Fasten the multivariate interpolation algorithm (MIP) to O(N logN) runtime complexity, while maintaining its approximation power, reaching the  optimal Trefethen rate for Bos-Levenberg-Trefethen functions (a type of analytic functions). 
• Extending the MIP interpolation technique to regular manifolds, by combining it with the global polynomial level set (GPLS) technique, which we have demonstrated to enable compuations of geometric quantities (mean and Gauss curvatures or ven 4th order terma like Laplacian of mean curvature) with machine precision.

Problem

While barycentric Lagrange interpolation  is known to be the optimal choice in 1D, enabling numerically stable interpolation up to degree= 1000.000 or more, in multi-dimensions, polynomial degrees of up to degree= 200 might be computable at most. That is why MIP extends 1D Newton interpolation, known to be stable in this range of degrees for Leja ordered nodes. 

MIP is based on a multi-dimensional extension of the classic Newton-divided difference scheme that computes the Newton interpolant of any function in quadratic runtime. In particular, MIP can compute formulas for the multivariate Lagrange polynomials in terms of multivariate Newton polynomials. Tthe basis change transformations are visualized in Fig.1

The transformations turn out to be very sparse and structured lower triangluar matrices, as  Additionally, the spectral differentiation matrices turn out to be sparse and almost diagonal with respect to the Newton basis.

Given that, I expect  the matrix vector product of the transformations to be computable with a complexity close to O(NlogN). Consequently, fast spectral differentiation and, thus,  a novel fast spectral PDE solver –FastSpec– results. I expect  FastSpec  to be compatible or superior in runtime to FFT, in relevant dimensions =2,3,…,7  and to be capable for addressing a large class of non-periodic PDE problems, involving BLT-functions. 

We further address the essential limitation of fast spectral PDE solvers of surfaces and general domains, given by their need of quadrilateral meshes. In combination with the GPLS technique we suggest to re-parametrize surface or manifold triangulations or polygonal domains to cubical (quadrilateral) meshes,  freeing FastSpec from mesh limitations.

Practical example

As initially motivated, the seek for fast spectral methods, addressing non periodic, high-dimensional PDE problems in (non-flat) domains is tremendous.

The applications  range from high-dimensional phase space simulations of Hamiltonian systems , Vlasov Equations, and Fokker-Planck systems to fluid dynamics of droplets, bio-physical cell and tissue morphology, and quantum droplets of Einstein-Bose condensates. 

Technology

• The project extends and is built on our Open Source Python package MINTERPY
• Applications for cell deformation and division processes together with our collaborators, Ivo F. Sbalazarini, MPI_CBG,CSBD, Dresen and Dan Fortunato CCM, NYC,USA

Outlook

If possible, please give a short outlook on the project, its impact and possible further research directions.

We expect our extension of the Poincaré–Steklov method to general triangulated domains, surfaces and manifolds, to performa superior to its current tensorial version when combined with FastSpec. The resulting computational power potentially shapers the landscape in computaional sciencs and its applications, as aforemtioned. 

Publications

• Hernandez Acosta,U., Thekke Veettil, S. K., Wicaksono,D.,  and Hecht,M.  minterpy – multivariate polynomial interpolation (Version 0.2.0-alpha (2023),  http://doi.org/10.14278/rodare.2062,  https://github.com/casus/minterpy/ 
• Veettil, Sachin Krishnan Thekke and Zavalani, Gentian and Acosta, Uwe Hernandez and Sbalzarini, Ivo F. and Hecht, Michael, Global Polynomial Level Sets for Numerical Differential Geometry of Smooth Closed Surfaces, SIAM Journal on Scientific Computing, 2023
• Hecht, Michael and Gonciarz, Krzysztof and Michelfeit, Jannik and Sivkin, Vladimir and Sbalzarini, Multivariate Interpolation in Unisolvent Nodes–Lifting the Curse of Dimensionality,, arXiv preprint arXiv:2010.10824, 2020
• Hecht, Michael and Sbalzarini, Ivo F., Fast Interpolation and {F}ourier Transform in High-Dimensional Spaces,Intelligent Computing. Proc. 2018 IEEE Computing Conf., Vol. 2,Springer Nature, 2018

Team

Lead

• Prof. Dr. Ivo F. Sbalzarini

Team Members

• Damar Wicaksono
• Azita Hajizada
• Gentian Zavalani
• Juan Esteban Suarez Cardona
• Janina Schreiber

Partners

• Dr. Daniel Fortunato, Ph.D, CCM, Simons Foundation, Flatiron Institute, NYC, USA
• Prof. Grady Wright, Ph.D,  Boise State University, USA, 
• Prof. Ivo F. Sbalzarini, MPI-CBG & CSBD, TUD, Dresden