A Cubed Sphere Fast Multipole Method

1. Problemstellung

Das Paper adressiert die effiziente Berechnung von Integraltransformationen auf der Kugeloberfläche $S \subset \mathbb{R}^3$, die bei der Diskretisierung von partiellen Differentialgleichungen und Faltungen in der Geophysik und Astrophysik auftreten. Das zugrundeliegende Problem ist die Berechnung von Summen über paarweise Partikelwechselwirkungen der Form:
$$\phi(x_i) \approx \sum_{j=1}^N K(x_i, x_j) w_j$$
wobei $K$ ein Kern (z. B. eine Greensche Funktion) ist und $w_j$ Gewichte darstellen. Eine direkte Berechnung dieser Summe erfordert $O(N^2)$ Operationen, was für große Partikelanzahlen $N$ (wie sie in modernen Simulationen üblich sind) prohibitiv teuer ist.

Herausforderungen bei bestehenden Methoden auf der Kugel sind:

• Sphärische Harmonische Transformationen (SHT): Diese erfordern oft Interpolation, wenn die Daten nicht auf einem Breitengrad-Längengrad-Gitter liegen, und können bei der Auflösung lokaler Merkmale hohe Kosten verursachen oder zu spurious Oszillationen führen.
• Bestehende FMM-Ansätze: Viele schnelle Multipolmethoden (FMM) für die Kugel basieren auf analytischen Reihenentwicklungen (z. B. für die Laplace-Greensche Funktion) oder erfordern die Auswertung des Kerns an Punkten außerhalb der Kugeloberfläche (z. B. in kartesischen Koordinaten). Dies ist problematisch, wenn der Kern nur auf der Kugel definiert ist (wie bei empirischen Geodaten) oder wenn die Auswertung außerhalb der Kugel mathematisch nicht wohldefiniert ist.

2. Methodik

Die Autoren stellen eine neue Version des Fast Multipole Method (FMM) vor, die speziell für die Kugel und das Cubed-Sphere-Gitter entwickelt wurde.

• Geometrie und Gitter: Die Kugel wird in ein Cubed-Sphere-Gitter unterteilt (Projektion der Flächen eines Würfels auf die umschriebene Kugel). Dies dient sowohl zur Diskretisierung des Integrals als auch zur Bildung der Cluster in der Baumstruktur.
• Baumstruktur: Es wird ein Quadtree verwendet, der aus den Cubed-Sphere-Zellen besteht. Jeder Knoten repräsentiert eine Cluster von Partikeln.
• Kernapproximation: Der entscheidende methodische Unterschied zu herkömmlichen FMMs ist die Verwendung von baryzentrischer Lagrange-Interpolation innerhalb der Gitterzellen anstelle von analytischen Multipolentwicklungen.
  • Die Interpolation erfolgt auf Chebyshev-Punkten innerhalb jeder Zelle.
  • Dies macht das Verfahren kernunabhängig (kernel-independent). Der Kern $K$ muss nur an Punkten auf der Kugel ausgewertet werden können.
• Interaktionstypen: Das Verfahren unterscheidet vier Interaktionstypen zwischen Ziel- (Target) und Quellen- (Source) Clustern:
  1. Partikel-Partikel (PP): Direkte Berechnung für nahe Cluster.
  2. Partikel-Cluster (PC): Approximation des Kerns in der Quellvariablen.
  3. Cluster-Partikel (CP): Approximation des Kerns in der Zielvariablen.
  4. Cluster-Cluster (CC): Approximation in beiden Variablen.
• Algorithmen:
  • CSFMM (Cubed Sphere FMM): Nutzt einen Dual-Tree-Traversierungsalgorithmus mit Aufwärts- und Abwärts-Pässen zur Berechnung von Fernfeld- und Nahfeld-Beiträgen.
  • CSTC (Cubed Sphere Tree Code): Eine Baum-Code-Variante (ähnlich Barnes-Hut) zur Vergleichszwecken, die nur Fernfeld-Approximationen für weit entfernte Cluster verwendet.

3. Wichtige Beiträge

1. Kernunabhängigkeit auf der Kugel: Das Verfahren benötigt keine analytischen Reihenentwicklungen des Kerns und keine Auswertungen außerhalb der Kugeloberfläche. Dies ermöglicht die Anwendung auf komplexe, empirische Kerne (wie bei Gezeitenberechnungen).
2. Integration des Cubed-Sphere-Gitters: Die Nutzung der Cubed-Sphere-Zellen als Basis für den Quadtree und die Interpolation bietet Vorteile wie nahezu gleich große Zellen und große Kreisbögen als Kanten, was die Interpolation stabilisiert.
3. Skalierbarkeit: Das CSFMM erreicht eine Komplexität von $O(N)$, während der Tree-Code (CSTC) $O(N \log N)$ erreicht. Beide sind deutlich schneller als die direkte Summation ($O(N^2)$).
4. Anwendungsbreite: Das Verfahren wurde erfolgreich auf vier verschiedene physikalische Probleme angewendet, die unterschiedliche Kerne erfordern.

4. Ergebnisse

Die Autoren testeten das Verfahren an folgenden Problemen:

• Poisson- und Biharmonische Gleichung:

  • Die numerischen Ergebnisse zeigen eine Konvergenz zweiter Ordnung bezüglich des Winkelschritts $\Delta\phi$ (entspricht erster Ordnung bezüglich $N$).
  • Der Approximationsfehler des CSFMM ist um Größenordnungen kleiner als der Diskretisierungsfehler des Mittelpunktschemas.
  • Für $N \approx 2.6 \times 10^6$ Partikel ist das CSFMM etwa 30-mal schneller als der Tree-Code und über 1000-mal schneller als die direkte Summation.

• Barotrope Wirbelgleichung (BVE):

  • Simulation von Rossby-Haurwitz-Wellen und Gaußschen Wirbeln auf einer rotierenden Kugel.
  • Die CSFMM-basierte Geschwindigkeitsberechnung liefert Ergebnisse, die mit der direkten Summation übereinstimmen, jedoch mit einem enormen Geschwindigkeitsvorteil (Faktor 36 bei feinstem Gitter).
  • Passive Tracer-Advektion zeigt die Stabilität des Verfahrens über mehrere Tage Simulation.

• Selbstanziehung und Belastung (SAL) in Gezeitenberechnungen:

  • Berechnung des SAL-Potentials basierend auf Meeresoberflächenhöhenanomalien.
  • Der Kern wird hier durch eine empirische Legendre-Reihe angenähert, die in eine geschlossene Form überführt wurde.
  • Das CSFMM konnte auf einem variablen hexagonalen Gitter mit über 2,3 Millionen Zellen angewendet werden. Die Ergebnisse stimmen qualitativ mit SHT-basierten Methoden überein, wobei das CSFMM eine glattere Lösung in Küstennähe liefert.

• Parallelisierung:

  • Die Implementierung nutzt MPI für die Parallelisierung der Partikel-Interaktionen.
  • Die Skalierung ist nahezu linear für kleine bis mittlere Prozessoranzahlen. Der Flaschenhals liegt in den seriell ausgeführten Aufwärts- und Abwärts-Pässen, was bei sehr hohen Prozessorzahlen die Effizienz begrenzt.

5. Bedeutung und Ausblick

Das Paper stellt einen signifikanten Fortschritt in der numerischen Strömungsmechanik auf der Kugel dar.

• Effizienz: Durch die Reduktion der Komplexität auf $O(N)$ ermöglicht das CSFMM hochauflösende Simulationen (z. B. in der Ozeanographie und Meteorologie), die mit direkten Methoden unmöglich wären.
• Flexibilität: Die Unabhängigkeit von spezifischen Kern-Analysen macht das Verfahren ideal für komplexe physikalische Modelle, bei denen die Kernfunktionen empirisch oder numerisch bestimmt sind (wie bei den Load Love Numbers für die Erdverformung).
• Zukünftige Arbeiten: Die Autoren planen die Integration des Verfahrens in Ozeanmodelle (MOM6), die Parallelisierung der Aufwärts-/Abwärts-Pässe und die Erweiterung auf flache Wasser-Gleichungen (Shallow Water Equations) mit adaptiver Gitterverfeinerung.

Zusammenfassend bietet die „Cubed Sphere Fast Multipole Method" eine robuste, skalierbare und präzise Alternative zu sphärischen Harmonischen und herkömmlichen FMMs für eine breite Klasse von Integraltransformationen auf der Kugel.