🌌 Barnes–Hut N-Körper

Gravitatives Softening ersetzt das 1/r²-Kraftgesetz durch 1/(r² + ε²), was verhindert, dass die Kraft ins Unendliche divergiert, wenn zwei Körper sich sehr nahe kommen. Ohne Softening würden nahe Begegnungen einen infinitesimal kleinen Zeitschritt zur genauen Integration erfordern, wodurch die Simulation abstürzt oder unsinnige „Schleuder“-Geschwindigkeiten erzeugt. Die Softening-Länge ε wird typischerweise auf einen Bruchteil des mittleren Teilchenabstands gesetzt; in realen kosmologischen Simulationen liegt sie bei etwa 1 kpc für Dunkle-Materie-Teilchen.

Der Quadtree hat O(n) Knoten und Tiefe O(log n). Für jeden der n Körper besucht der Baumdurchlauf im Durchschnitt O(log n) Knoten, bevor genügend Zellen das θ-Kriterium erfüllen. Multipliziert ergibt das O(n log n) Kraftauswertungen pro Schritt. Auch der Aufbau des Baumes selbst kostet O(n log n). In der Praxis sind die konstanten Faktoren klein, und für n = 10.000 liegt die Beschleunigung gegenüber O(n²) bei etwa dem 100- bis 1.000-Fachen.

Wenn zwei Galaxien einander durchdringen, reißen Gezeitenkräfte Sterne aus den Außenbereichen und schleudern sie in lange „Gezeitenschweife“ und Brücken, die sich über Millionen Lichtjahre erstrecken. Der Prozess wird fast ausschließlich von der Schwerkraft bestimmt; die Sternscheiben durchdringen einander weitgehend ungehindert, weil Sterne so weit voneinander entfernt sind. Die Milchstraße und die Andromeda-Galaxie befinden sich auf Kollisionskurs und werden voraussichtlich in etwa 4,5 Milliarden Jahren verschmelzen, wodurch eine ähnliche Gezeitenschweif-Struktur entsteht, wie sie in dieser Voreinstellung sichtbar ist.

Die Simulation zeigt die Anzahl der Barnes-Hut-Auswertungen neben den naiven n(n–1)/2 Vergleichen, die für die direkte Summierung nötig sind. Für n = 500 und θ = 0,7 wertet Barnes-Hut typischerweise etwa 3.000–5.000 Kraftpaare pro Körper und Schritt aus statt 499, was eine 50–100× Beschleunigung ergibt. Mit wachsendem n verstärkt sich der Vorteil: Bei n = 2.000 benötigt die naive Methode fast 2 Millionen Paarauswertungen pro Schritt, während Barnes-Hut nur etwa 20.000 benötigt.

Kinetische Energie KE = Σ ½mᵢvᵢ² und gravitative potentielle Energie PE = –Σᵢ≠ⱼ Gmᵢmⱼ/rᵢⱼ (summiert über alle Paare). In einer echten konservativen Simulation sollte die Gesamtenergie E = KE + PE konstant sein, doch numerische Integration führt Fehler ein. Der hier verwendete Leapfrog-(Verlet-)Integrator ist symplektisch, das heißt, er erhält ein modifiziertes Hamilton-Funktional und hält die langfristige Energiedrift sehr gering. Die beobachteten Schwankungen sind teils echte physikalische Austausche (z. B. tauscht ein Körper auf exzentrischer Bahn KE gegen PE) und teils numerischer Rundungsfehler durch endliches dt.

Wenn Sie „θ-Abstieg für ausgewählten Körper hervorheben“ aktivieren, zeigt ein Klick auf einen Körper, welche Quadtree-Zellen er annähert bzw. rekursiv durchläuft. Dieselbe Quadtree-Zelle kann für Körper an unterschiedlichen Positionen unterschiedlich behandelt werden, was zeigt, dass Barnes-Hut ein adaptiver Algorithmus ist. Für Chaos in den tatsächlichen N-Körper-Trajektorien nutzen Sie den Zwei-Trajektorien-Vergleich in verwandten Simulationen: Selbst eine Störung von Δ = 10⁻⁵ in den Anfangsbedingungen führt zu exponentiell divergierenden Bahnen, was zeigt, dass das N-Körper-Problem im Allgemeinen chaotisch ist.

Ja — die GADGET-Codefamilie (Springel 2001, 2005) verwendet einen hierarchischen Baum, der Barnes-Hut sehr ähnlich ist, und wurde zur Simulation der Millennium-Simulation (10 Milliarden Teilchen) und der IllustrisTNG-Galaxienentstehungsläufe eingesetzt. Moderne Codes kombinieren Barnes-Hut oft mit Fast-Multipole-Methoden (FMM), Particle-Mesh-(PM)-Techniken oder GPU-Parallelismus, um bis zu 10¹² Teilchen zu simulieren. Der Algorithmus wird auch außerhalb der Astrophysik eingesetzt, in der Molekulardynamik, Strömungssimulation und beim Rendern dichter Partikelsysteme.

Jeder innere Knoten des Quadtrees speichert die Gesamtmasse M = Σmᵢ und die massegewichtete mittlere Position r_cm = Σmᵢrᵢ / M aller Körper innerhalb dieser Zelle. Wird eine entfernte Zelle angenähert, wird die gravitative Kraft auf Körper i so berechnet, als wäre die gesamte Masse dieser Zelle bei r_cm konzentriert. Diese Einzel-Pol-Näherung ist bis zur ersten Ordnung in s/d genau; Multipolentwicklungen höherer Ordnung (Quadrupol, Oktupol) können für bessere Genauigkeit auf Kosten von mehr Speicher und Rechenaufwand einbezogen werden.