Schnelle Spektralmethoden für hochdimensionale Räume und reguläre Mannigfaltigkeiten

Projekttitel: Schnelle Spektralmethoden für hochdimensionale Räume und reguläre Mannigfaltigkeiten

Forschungsbereich: Mathematische Grundlagen und statistisches Lernen

Die Schönheit und die faszinierende Rätselhaftigkeit, die komplexe Systeme verkörpern, könnten die treibende Kraft hinter den Ambitionen vieler Wissenschaftler in ihrem Forschungsgebiet sein. Die Überwindung des rechnerischen Engpasses bei den heute behandelten wissenschaftlichen Fragestellungen erweist sich als das zentrale Thema.

Dieser Engpass ergibt sich aus der Notwendigkeit, Funktionsdaten präzise und effizient in geschlossene Ausdrücke zu entwickeln, um allgemeine PDE-Probleme zu lösen. Obwohl die weit verbreitete Überzeugung besteht, dass eine polynomiale Interpolation zur Bewältigung dieser Aufgabe nicht durchführbar sei, lässt sich hier Prof. Lloyd N. Trefethen zitieren, der dieses Missverständnis aufgreift:

„… man kann zeigen, dass die Interpolation durch Polynome in Tschebyscheff-Punkten äquivalent ist zur Interpolation periodischer Funktionen durch Sinus- und Kosinusreihen in gleichmäßig verteilten Punkten. Letzteres ist Gegenstand der diskreten Fourier-Analyse, und man kommt nicht umhin festzustellen: Während weitverbreitet der Verdacht besteht, dass es nicht sicher sei, mit Polynomen zu rechnen, macht sich niemand Sorgen um die schnelle Fourier-Transformation (FFT)! Letztendlich ist dies vielleicht der größte Unterschied zwischen Fourier- und Polynom-Interpolanten: der Unterschied in ihrem Ruf.“ (Trefethen, L.N. (2019), Approximation theory and approximation practice, Band 164, SIAM.)

Wir schlagen vor, die Bemühungen fortzusetzen, FFT-basierte Methoden auf nichtperiodische Funktionen zu übertragen, indem multivariate Polynominterpolationstechniken genutzt werden, die dem Fluch der Dimensionalität widerstehen. Unsere Strategien deuten auf die Implementierung einer neuen Generation schneller Spektralmethoden hin, die die Anwendbarkeit FFT-basierter Verfahren auf nichtperiodische Probleme erweitern und sich in hohen Dimensionen (dim = 2, …, 6, 7) hinsichtlich der Laufzeit als den FFT-basierten pseudospektralen Methoden überlegen erweisen.

Ziele

Im Jahr 2000 stellten die SIAM-Gastredakteure Jack Dongarra und Francis Sullivan eine Liste zusammen, die sie als die „Top-Ten-Algorithmen des Jahrhunderts“ bezeichneten. (Dongarra, J. und F. Sullivan (2000). Top-Ten-Algorithmen des Jahrhunderts. Computing in Science and Engineering)

Es überrascht nicht, dass zwei Algorithmen dieser bedeutenden Liste das Herzstück schneller (Pseudo-)Spektralmethoden bilden: die schnelle Fourier-Transformation (FFT) und die schnellen Multipolmethoden (FMMs). Der Artikel schließt mit den Worten:

„Welche neuen Erkenntnisse und Algorithmen wird das 21. Jahrhundert bringen? Die vollständige Antwort wird natürlich erst in weiteren hundert Jahren bekannt sein. Eines scheint jedoch sicher zu sein“… „Das neue Jahrhundert wird für uns nicht sehr erholsam sein, aber es wird auch nicht langweilig werden!“

Wir konzentrieren uns darauf, die Anwendbarkeit schneller Spektralmethoden zu erweitern, indem wir nicht nur bestehende Einschränkungen wie die Notwendigkeit der Periodizität bei FFTs oder den quadratischen Abfall des Coulomb-Feldes bei FMMs angehen, sondern diese Methoden auch auf hohe Dimensionen ausweiten – unter Beibehaltung ihrer Effizienz und unter Vermeidung eines exponentiellen Anstiegs der Laufzeit und der Speicherkomplexität. Zwei unserer eigenen Ergebnisse ergänzen dieses Bestreben und reihen sich in aktuelle Beiträge auf diesem Gebiet ein:

• Die Laufzeitkomplexität des multivariaten Interpolationsalgorithmus (MIP) auf O(N log N) zu begrenzen und dabei seine Approximationsleistung beizubehalten, wobei die optimale Trefethen-Rate für Bos-Levenberg-Trefethen-Funktionen (eine Art analytischer Funktionen) erreicht wird.
• Erweiterung der MIP-Interpolationstechnik auf reguläre Mannigfaltigkeiten durch Kombination mit der Global-Polynomial-Level-Set-Technik (GPLS), von der wir gezeigt haben, dass sie Berechnungen geometrischer Größen (mittlere und Gaußsche Krümmung oder sogar Terme vierter Ordnung wie der Laplace-Operator der mittleren Krümmung) mit Maschinenpräzision ermöglicht.

Problemstellung

Während die baryzentrische Lagrange-Interpolation bekanntermaßen die optimale Wahl in einer Dimension ist und eine numerisch stabile Interpolation bis zu einem Grad von 1.000.000 oder mehr ermöglicht, sind in mehrdimensionalen Fällen Polynomgrade von höchstens 200 berechenbar. Aus diesem Grund erweitert MIP die 1D-Newton-Interpolation, die in diesem Gradbereich für Leja-geordnete Knoten als stabil gilt.

MIP basiert auf einer mehrdimensionalen Erweiterung des klassischen Newton-Schemas mit geteilten Differenzen, das den Newton-Interpolanten einer beliebigen Funktion in quadratischer Laufzeit berechnet. Insbesondere kann MIP Formeln für die multivariaten Lagrange-Polynome in Form von multivariaten Newton-Polynomen berechnen. Die Basiswechsel-Transformationen sind in Abb. 1 dargestellt.

Die Transformationen erweisen sich als sehr spärliche und strukturierte untere Dreiecksmatrizen, da außerdem die spektralen Differenzierungsmatrizen in Bezug auf die Newton-Basis spärlich und nahezu diagonal sind.

Vor diesem Hintergrund gehen wir davon aus, dass das Matrix-Vektor-Produkt der Transformationen mit einer Komplexität nahe O(NlogN) berechenbar ist. Daraus ergibt sich eine schnelle spektrale Differenzierung und somit ein neuartiger, schneller spektraler PDE-Löser – FastSpec. Wir gehen davon aus, dass FastSpec in den relevanten Dimensionen = 2, 3, …, 7 hinsichtlich der Laufzeit mit der FFT vergleichbar oder dieser überlegen ist und in der Lage ist, eine große Klasse nichtperiodischer PDE-Probleme unter Einbeziehung von BLT-Funktionen zu lösen.

Wir befassen uns ferner mit der wesentlichen Einschränkung schneller spektraler PDE-Löser für Oberflächen und allgemeine Bereiche, die sich aus deren Notwendigkeit von Vierecknetzen ergibt. In Kombination mit der GPLS-Technik schlagen wir vor, Oberflächen- oder Mannigfaltigkeits-Triangulationen bzw. polygonale Bereiche auf kubische (Viereck-)Netze umzuparametrisieren, wodurch FastSpec von Netzbeschränkungen befreit wird.

Praxisbeispiel

Wie bereits eingangs dargelegt, besteht ein enormer Bedarf an schnellen spektralen Methoden zur Lösung nichtperiodischer, hochdimensionaler PDE-Probleme in (nicht-flachen) Bereichen.

Die Anwendungsbereiche reichen von hochdimensionalen Phasenraumsimulationen von Hamilton-Systemen, Vlasov-Gleichungen und Fokker-Planck-Systemen bis hin zur Strömungsdynamik von Tröpfchen, der biophysikalischen Zell- und Gewebemorphologie sowie Quantentröpfchen aus Einstein-Bose-Kondensaten.

Technologie

• Das Projekt baut auf unserem Open-Source-Python-Paket MINTERPY auf und erweitert dieses.
• Anwendungen für Zellverformungs- und Zellteilungsprozesse in Zusammenarbeit mit unseren Partnern Ivo F. Sbalazarini, MPI_CBG, CSBD, Dresden, und Dan Fortunato, CCM, New York, USA

Ausblick

Wir gehen davon aus, dass unsere Erweiterung der Poincaré-Steklov-Methode auf allgemeine triangulierte Bereiche, Flächen und Mannigfaltigkeiten in Kombination mit FastSpec eine bessere Leistung erzielen wird als die derzeitige Tensorversion. Die daraus resultierende Rechenleistung könnte, wie bereits erwähnt, die Landschaft der Computerwissenschaften und ihrer Anwendungen grundlegend verändern.

Publikationen

• 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

Teamleitung

• Prof. Dr. Ivo F. Sbalzarini

Teammitglieder

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

Partner

• 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, Tech