Galaxien auf Kollisionskurs. Graviationssimulation von Mehrkörperproblemen und Entwicklung einer Scriptsprache zum Beschreiben gravitativer Konstellationen

Inhaltsverzeichnis

Einleitung

1 Konzeption von Gravius 2.0

2 Ansätze zur näherungsweisen Lösung von Mehrkörperproblemen
2.1 Theoretische Vorüberlegungen
2.2 Das Eulerverfahren
2.3 Das Runge-Kutta-Verfahren
2.4 Der Barnes-Hut-Algorithmus

3 Umsetzung des Barnes-Hut-Algorithmus
3.1 Finden der Root-Zelle
3.2 Aufbau des Octree
3.3 Zuweisung der Schwerpunkte
3.4 Berechnung der Kräfte
3.5 Integration der Bewegungen

4 Die Scriptsprache GSC zur Beschreibung einer Szene
4.1 Einführung in die Funktionen
4.2 Die statische Objektdefinition
4.3 Dynamische Eigenschaften und Objektgruppen
4.4 Hierarchie im Universum
4.5 Zusammenführen einer Szene
4.6 Details zu eingebettetem Java-Code

5 Visualisierung der Simulationen

6 Kollision zweier Galaxien in Gravius 2.0

7 Realitätsanspruch am Beispiel einer Galaxie

Zusammenfassung

Anhang

Literatur

Internetquellen

Bildquellen

Einleitung

In jeder Stunde nähert sich unsere Galaxie, die Milchstraße, dem Andromedanebel um 400.000 .m . Lau t de r USRaumfahrtbehörde Nasa werden die Galaxien in ca. 4 Milliarden Jahren kollidieren. Nach weiteren 2 Milliarden Jahren sollen sie sich dann zu einer neuen, elliptischen Galaxie vereinigt haben. [I1]

Solche Vorgänge sind in der Entwicklung des Universums bis heute keine Besonderheit und haben eine große Bedeutung in der Strukturbildung der Materie. Trotzdem sind sie äußerst komplex und schwer vorstellbar. Mit solchen Problemen beschäftigten wir uns in der Jugend forscht - Arbeit 2012 „Planeten in Aktion - Gravita- tionssimulation von Mehrkörperproblemen“, im Rahmen derer wir eine Simulationssoftware namens Gravius 1.0 erstellten, mit welcher wir auch erfolgreich kleinere Szenarien mit bis zu 500 Körpern berechnen konnten. Beim Entwickeln dieses Programms konzentrierten wir uns besonders auf die physikalischen Grundlagen und stießen recht schnell an die Grenzen unseres einfachen Algorithmus, welcher nicht auf die Simulationen großer Körperan- zahlen ausgelegt war. Eine umfassende Simulation, wie beispielsweise die Kollision zweier Galaxien, konnten wir damit nicht verwirklichen.

Dies motivierte uns, Gravius 1.0 im Rahmen der vorliegenden Arbeit zu Gravius 2.0 weiterzuentwickeln, sodass es leistungsstärker und einfacher in der Benutzung werden würde.

Wir beschlossen dennoch, ein völlig neues Programm zu schreiben und es somit von Grund auf zu optimieren, denn wie ein französisches Sprichwort sagt: „Um weiter zu springen, muß man einen Schritt zurücktreten.”. Einzig und allein die Erfahrungen beim Erstellen von Gravius 1.0 übernahmen wir in das neue Projekt. Um dem Ziel einer höheren Effizienz der Simulation näher zu kommen, nahmen wir uns vor, einen neuen Algorithmus für die Berechnung zu implementieren. Ferner planten wir zur Verbesserung der Benutzerfreundlichkeit die Entwicklung einer Scriptsprache zum Beschreiben von Szenen.

Bei der Erstellung dieser Arbeit danken wir Herrn Udo Weitz für den fachlichen Beistand im Bereich der Informatik, Herrn Robert Müller für die Betreuung in der Physik und unseren Freunden und Verwandten für die mentale Unterstützung sowie für Hinweise bezüglich der schriftlichen Ausarbeitung. Außerdem sprechen wir hiermit Herrn Martin Reidemeister unseren Dank für die Bereitstellung seiner Diplomarbeit aus.

Im besonderen Maße danken wir Sir Isaac Newton für die Herleitung und Formulierung des Gravitationsgesetzes.

1 Konzeption von Gravius 2.0

Zur Umsetzung der Ziele entschieden wir uns für eine Modularisierung des Programms in drei Teile, damit jeder einzeln entwickelt werden konnte. Somit gliederten wir Gravius 2.0 in die Module Simulation, Scriptengine und Visualisierung, welche in der grafischen Benutzeroberfläche zusammengeführt wurden. Um die Simulation, im Vergleich zu Gravius 1.0, effizienter zu gestalten, implementierten wir den Barnes-Hut- Algorithmus, welcher beim Lösen des N-Körperproblems Anwendung findet. Mittels der Programmiersprache Java war es uns möglich, den Algorithmus so umzusetzen, dass wir tatsächlich eine große Leistungssteigerung erreichten.

Mit Gravius 1.0 war es sehr zeitaufwändig, komplexe Szenen zu erstellen, da die Eigenschaften jedes Körpers (Position, Geschwindigkeit, etc.) manuell festgelegt werden mussten. Sollte eine Szene mit vielen Objekten eine bestimmte Struktur aufweisen, beispielsweise eine ringförmige Anordnung der Körper, wie in einem Asteroidengürtel, so war es fast unmöglich, dies in einer angemessenen Zeit zu realisieren. Daher entwarfen wir eine Scriptsprache zum Beschreiben von Szenen, in denen ähnliche Objekte in Gruppen zusammengefasst und strukturelle Anordnungen unkompliziert umgesetzt werden können. Somit ist es möglich, bestimmte Eigenschaften für diese Gruppen und nicht nur für Einzelobjekte zu definieren.

Die Umsetzung dieser Scriptsprache gelang uns mit dem Implementieren einer Scriptengine, welche aus einer Szenenbeschreibung eine konkrete Szene erzeugt.

Die Visualisierung der Simulation als drittes Modul ist ein essentieller Bestandteil von Gravius, da die Anschaulichkeit der simulierten Werte einer Szene bestens über eine grafische Darstellung erreicht werden kann. Letztendlich machte es die Modularisierung des Programms notwendig, gewisse Schnittstellen für den Transport der Daten zwischen den Modulen zu entwickeln. In der Umsetzung sind dies Dateiformate für die Speicherung von Szenen und Simulationen.

Von der Scriptengine erzeugte Dateien können von den Modulen der Simulation und Visualisierung geöffnet und anschließend verwendet bzw. als Vorschau angezeigt werden. Die Darstellung der vom Simulationsmodul geschriebenen Dateien ist ebenfalls durch das Visualisierungsmodul möglich.

2 Ansätze zur näherungsweisen Lösung von Mehrkörperproblemen

2.1 Theoretische Vorüberlegungen

Ziel dieser Arbeit war es, eine N-Körper-Simulation zu entwerfen und zu implementieren. N-Körperprobleme befassen sich mit der annähernden Lösung der Bewegungsgleichungen von mehr als zwei Körpern, die aufgrund ihrer Massen gravitativ in Wechselwirkung stehen.

Basis für diese Bewegungsgleichungen ist eine Differentialgleichung zweiter Ordnung. Sie beschreibt die Beschleunigung, welche auf ein Objekt im Gravitationsfeld wirkt:

Abbildung in dieser Leseprobe nicht enthalten

Ausgehend von einer klar definierten Anfangssituation, mit festen Massen, Positionen und Geschwindigkeiten, wird simuliert, wie sich das System mit der Zeit entwickelt.

Ein 2-Körperproblem ist eindeutig lösbar und reicht zum Beschreiben einiger tatsächlicher astronomischer Kon- stellationen aus. Dies gilt auch für Spezialfälle des 3-Körperproblems, bei denen einer der Körper eine vernach- lässigbar kleine Masse hat. Das allgemeine 3-Körperproblem und infolgedessen jedes weitere N-Körperproblem können nur noch numerisch angenähert werden. Es gibt eine Vielzahl von Verfahren, welche die Lösung solcher Probleme approximieren.

In Gravius 2.0 haben wir das klassische Runge-Kutta-Verfahren ebenso wie das Euler-Verfahren implementiert. Beide sind im Zuge der Optimierung mit dem Barnes-Hut-Algorithmus gekoppelt worden.

2.2 Das Eulerverfahren

Das Eulerverfahren ist die einfachste Methode zur numerischen Berechnung von gravitativen Mehrkörperproble- men.

Im Prinzip wird die Differentialgleichung, die das Potential am Ort eines Objekts beschreibt, in zwei Differential- gleichungen aufgeteilt, die durch einfache Multiplikation mit der Zeitdifferenz näherungsweise integriert werden:

Abbildung in dieser Leseprobe nicht enthalten

2.3 Das Runge-Kutta-Verfahren

Problematisch am Eulerverfahren ist, dass die Ableitungen für das gesamte Zeitintervall Δt als konstant angesehen werden. Ziel des Runge-Kutta-Verfahrens ist es, genau an dieser Stelle eine Verbesserung zu erreichen. Dazu wird nicht nur eine Stelle im Zeitintervall beachtet, sondern vier: Zunächst einmal an der Ausgangsposition, dann zwei mal in der Hälfte des Intervalls und schließlich einmal am Ende. Aus den gewichtet gemittelten Werten für die jeweiligen Stellen im Intervall wird anschließend durch Multiplikation mit der Zeitdifferenz die genauere Geschwindigkeits- und Wegänderung ermittelt.

Das auf Mehrkörperprobleme und damit auf Differentialgleichung zweiten Grades angepasste Runge-Kutta-Verfahren kann folgendermaßen formuliert werden¹:

Abbildung in dieser Leseprobe nicht enthalten

Der Vorteil des Runge-Kutta-Verfahrens gegenüber dem Euler-Verfahren zeigt sich besonders in der Fehlerbetra- chtung: Ersteres ist mit dem lokalen Fehler Δt5 behaftet, während letzteres den wesentlich ungünstigeren lokalen Fehler Δt2 aufweist. Für kleine Δt konvergiert demnach das Runge-Kutta-Verfahren viel stärker als das Euler- Verfahren.²

2.4 Der Barnes-Hut-Algorithmus

Im klassischen N-Körperproblem steht jeder Körper mit jedem anderen in Wechselwirkung, weshalb sich eine Gesamtzahl von N · (N − 1) zu berechnenden Kräften oder Beschleunigungen für jeden Körper ergibt. Daraus folgt die große, dennoch polynomiale Zeitkomplexität von O(N2). Da der quadratische Rechenaufwand die Simulation für größere Körperanzahlen sehr ineffektiv macht und die Parallelisierung dieses Problems die Effizienzgrenze lediglich verschiebt, haben wir den Barnes-Hut-Algorithmus in unserem Programm implementiert, um die Ef- fizienz tatsächlich zu steigern.

Dieser Algorithmus ist ein Näherungsverfahren zur Berechnung von Kräften in N-Körperproblemen, welches 1986 von Josh Barnes und Piet Hut veröffentlicht wurde.

Die Anzahl der zu berechnenden Kräfte wird durch das Zusammenfassen von Teilchengruppen zu einem neuen Pseudoteilchen, welches ausschließlich für die Berechnung relevant ist, verringert (siehe Abbildung 1). Der Grundgedanke des Barnes-Hut-Algorithmus ist es, die Summe der Kräfte anzunähern, welche die einzelnen Körper (Teilchen) einer Gruppe auf einen anderen, der Gruppe nicht zugehörigen Körper, ausüben. Dazu wird die einzelne Kraft vom betrachteten Teilchen zum Massenschwerpunkt der Gruppe verwendet. Damit der Fehler, der durch die Vereinfachung auftritt minimal bleibt, gibt es das Multipol-Akzeptanz-Kriterium. Dieses muss erfüllt sein, um die Summe der Einzelkräfte statt der Kraft zum ermittelten Pseudoteilchen zu berech- nen. Als Multipol-Akzeptanz-Kriterium bezeichnet man das Verhältnis vom Durchmesser d zum Abstand r der Grupped r.Wenndieseseinenbestimmten,vorherfestgelegtenSchwellwertθüberschreitet,solltedieNäherung nicht verwendet werden, um größere Fehler zu vermeiden. Je kleiner θ ist, desto genauer ist die Simulation, was im

Grenzfall θ =0wieder die Aufsummierung aller Einzelkräfte bedeutet. Für die Effektivität dieser Näherungsvariante ist eine geschickte Wahl von θ erforderlich.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1: Vereinfachung einer Teilchengruppe, durch ein Pseudoteilchen mit Punktmasse (zweidimensionales Beispiel)

Ausgangspunkt für den Algorithmus ist eine vorgegebene Verteilung der Teilchen im dreidimensionalen Raum. Anfangs werden die Körper hierarchisch, in Form eines Octrees, strukturiert. Ein Octree ist eine Baumstruktur, bei der in jeder Ebene von jedem Knoten acht Äste abgehen, die aber auch leer sein können. Der Raum wird für diesen Vorgang in acht Zellen eingeteilt, welche die ersten acht Äste des Octree darstellen. Befindet sich in einem dieser Oktanten mehr als ein Teilchen, so wird dieser wieder in acht Zellen aufgeteilt, die als acht neue Äste am Knoten des aufgeteilten Oktanten, in der Baumstruktur auftauchen. Dieser Vorgang wird weitergeführt, bis jeder Körper einem eigenen Unteroktanten zugeordnet werden kann (siehe Abbildung 2).

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2: Unterteilung des Raumes zum einzelnen Erfassen der Objekte anhand eines zweidimensionalen Beispiels

Nachdem der Baum nun Information über die räumliche Verteilung der Teilchen beinhaltet, wird die Masseverteilung des Octree berechnet. Dabei wird für jeden Knoten des Baumes die Gesamtmasse und der Massenschwerpunkt ermittelt.

Mithilfe dieser Werte werden die Kräfte, die auf die Teilchen wirken, errechnet. Durch diese Kraftberechnung, erreicht der Barnes-Hut-Algorithmus einen wesentlichen Geschwindigkeitsvorteil gegenüber der klassischen Betrachtung aller Wechselwirkungen.

Es wird überprüft, obdr bezüglicheinesKörpersundeinesKnotensunterdemvorherfestgelegtenSchwellwertθ liegt. Ist dies der Fall, so wird die Kraft mit Hilfe der Knotenmasse und dem Massenschwerpunkt berechnet. Liegt der Wert von θ darüber, so wird diese Betrachtung analog für alle Unteroktanten durchgeführt. Durch dieses Verfahren ist es möglich, eine erhebliche Anzahl von Berechnungen durch einige wenige zu ersetzen. Der Rechenaufwand der Kraftberechnungen sinkt somit auf O(N · log(N)), da ein Baum aufgebaut wird, welcher log(N) Schichten hat, und man für jeden der N Körper diese Schichten betrachtet. Das Aufbauen des Baumes, in jedem Rechenschritt vorgenommen, vervielfacht den Rechenaufwand um einen konstanten Faktor und ist somit zu vernachlässigen.

Aufgrund der Komplexität von O(N · log(N)) haben wir den Barnes-Hut-Algorithmus der klassischen Kräfteberechnung mit der Komplexität O(N2) vorgezogen und in Gravius implementiert.

[...]

¹ Siehe [L5]

² Siehe [L3] (S. 51 ff.)