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.
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:
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.
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.
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.