diff options
Diffstat (limited to 'main.tex')
| -rw-r--r-- | main.tex | 463 |
1 files changed, 463 insertions, 0 deletions
diff --git a/main.tex b/main.tex new file mode 100644 index 0000000..dee760e --- /dev/null +++ b/main.tex @@ -0,0 +1,463 @@ +\documentclass[a4paper, 10pt]{article} +\usepackage[top=2cm, bottom=2cm, left=1.5cm, right=1.5cm]{geometry} +\usepackage[utf8]{inputenc} +%\usepackage[english]{babel} +\usepackage[german]{babel} + +\usepackage{amsmath} +\usepackage{amsfonts} +\usepackage{amsthm} + +\usepackage[hidelinks]{hyperref} +\usepackage{graphicx} +\usepackage{caption} +\usepackage{lmodern} +\usepackage{tikz} +\usepackage{multicol} +\usepackage{lipsum} + +\usepackage{listings} +\usepackage{listings-golang} + +\lstset{ + frame=single, + language=golang, +} + +\linespread{1} + +\newcommand{\rarrow}{\( \rightarrow \)} + +\begin{document} + +\title{\huge Galaxy Simulation\\ \large Jugend Forscht 2018/2019} +\date{2018 - 2019} +\author{Emile Hansmaennel}%\\ Theodor-Fliedner-Gymnasium, Heinrich Heine +%Universität Düsseldorf} + +\maketitle + +\begin{multicols*}{2}[ +\abstract{ + \parbox{0.85\textwidth}{ + \centering + \parbox{0.6\textwidth}{ + \centering + \bigskip + Ist es möglich die Entstehung von Galaxien zu simulieren? Um +diese Frage zu beantworten bin ich zu dem Schluss gekommen, dass ich das doch +einfach mal ausprobieren sollte. Dazu habe ich das Navarro-Frenk-White Profil +implementiert um anschließen die Kräfte die Zwischen den Sternen wirken zu +berechnen. Dabei stattete ich die Sterne mit einer zufälligen Masse aus und +Unterteilte die Galaxie in dynamisch-große Zellen um die Simulation stark zu +beschleunigen. Um eine Stabile Galaxie zu simulieren müssen jedoch alle Sterne +in der Galaxie eine Anfangsgeschwindigkeit besitzen die sie auf eine Kreisbahn +lenkt, damit die Kraft, welche die Sterne in die Mitte der Galaxie zieht +ausgeglichen werden. + \bigskip + } + } +} +] + +\renewcommand{\contentsname}{Inhaltsverzeichnis} \tableofcontents[Inhalt] + +\section{Einleitung} +Das Projekt ist nach meinem vorletzten Jugend-Forscht Projekt entstanden: Ich +habe ein Praktikum in Astronomischen Recheninstitut in Heidelberg genutzt, um +mit einem Doktoranden\footnote{Tim Tugendhat} das Navarro-Frenk-White Profil, +das zum generien von Punktwolken genutzt wird, zu visualizieren. Anschließend +hat sich das Projekt ein bisschen verlaufen, irgendwann beschloss ich jedoch, +dass das Projekt weiterzuführen und statt nur statische Galaxien zu generieren +dazu überzugehen die Galaxien zu simulieren, also die Entwicklung einer +virtuellen Galaxie zu untersuchen. Eines der Entscheidenden Probleme war die +Laufzeit der Simulation. Das Problem das es zu lösen galt, war die nutzung von +mehreren Threads mit der nutzung des Barnes-Hut Algorithmus zu kombinieren. +Das Ergebniss ist sehr schön: Durch die nutzung der Programmiersprache Golang +war das einbauen der nutzung von mehreren Threads vergleichsweise einfach. + +\section{Vorgehensweise} + +Wie schon in der Einleitung beschrieben habe ich mehrere Techniken kombiniert +um mein Ziel zu erreichen. Das komplette Projekt lässt sich in mehrere +Abschnitte unterteilen: Die Generierung der Punktwolke, aus der eine Galaxie +abstrahiert wird. Die Simulation der Galaxie bei der die Kräfte die in der +Galaxie wirken berechnet werden und daraus die Geschwindigkeit und Richtung in +die der Stern fliegt. + +\section{Generieren} + +Das Generieren der Statischen Punktwolke aus der die Galaxie abstrahiert wird +ist ein wichtiger Bestandteil des Gesamtprojektes, denn alles baut auf ihr auf. +Kurz: um Kräfte zwischen Sternen zu berechnen braucht man erstmal Sterne! + +\subsection{Das Navarro-Frenk-White Profil} +Das Navarro-Frenk-White Profil (NFW-profil) ist ein Profil zur Generierung von +Koordinaten in n-Dimensionalen Systemen. Das Profil gibt einem die +Warscheinlichkeit \( \rho \) zurück, dass ein Punkt im Abstand \( r \) zum +Mittelpunkt des raumes existiert. Die dazugehörige Funktion sieht wiefolgt +aus: + +\begin{equation} \label{eq:NFW_profile} + \rho_{NFW}(r) = \frac{ 1 }{ \sqrt{ 2 \pi } \cdot \sigma } \cdot + \exp \left( \frac{ -\phi(r) }{ \sigma^{ 2 } } \right) +\end{equation} + +\begin{equation*} + \phi(r) = \frac{ 4\pi \cdot G \cdot f_{0} \cdot R_{s}^3 }{ r } \cdot + ln{ \left( 1 + \frac{ r }{ R_{s} } \right) } +\end{equation*} + +Möchte man nun herausfinden wie weit ein Punkt mit der Koordinate \( (x_1, x_2, +... , x_n) \) mit \( x \in \mathbb{N} \) vom Mittelpunkt des Raumes entfernt +ist, kann der Satz des Pythagoras (\ref{eq:pythagoras}) verwendet werden. + +\begin{equation} \label{eq:pythagoras} +r_n = \sqrt{\sum_{i=0}^{n} x_i^2} \qquad n \in \mathbb{N} +\end{equation} + +Der Abstand \( r \) zum Mittelpunkt des Raumes kann nun in das NFW-Profil +\ref{eq:NFW_profile} gegeben werden wodurch ein Wert \( s \) entstehet: + +\begin{equation} +\rho_{NFW}(r) = \dots = s +\end{equation} + +Dieser Wert \( s \) stellt die Warscheinlichkeit dar, das ein Stern der +eine Entfernung \( r \) vom Mittelpunkt der Galaxie besitzt existiert. + +Die Galaxie Wirkt nun aus der Ferne wie ein Würfel, da die aus \( \rho \) +retultierende Kurve aprubt endet. Dies kann gelöst werden, indem statt \( +\rho_{NFW}(r) \) folgendes gerechnet wird: \( \rho_{NFW}(r) - +\rho_{NFW}(r_{max}) \) + +\subsection{Random Sampling} +Sei \( s \) ein zufälliger Wert im Intervall \( \psi = [ \rho(r_{min}); \rho(r_{max}) ] +\). Generiert man nun einen zufälligen Wert \( r \) im Intervall \( \psi \), +kann man schauen ob \( s > r \lor s < r \) gilt. Ist \( r > s \), wird der Stern verworfen, +ist \( r < s \) wird der Stern behalten. + +\subsection{Lookup Tabellen} +Statt bei der generierung eines Punktes jedes mal das NFW-Profil +(\ref{eq:NFW_profile}) anzuwenden, kann das NFW-Profil für einen Bereich +vorberechnet werden und in einer Tabelle abgespeichert werden. Somit kann wenn +eine Entfernung \( r \) zum Mittelpunkt des Raumes vorliegt der entsprechende +Wert aus der Tabelle ausgelesen werden. Die Tabelle kann jedoch nicht so +genaue Ergebnisse liefern wie das NFW-Profil, sie kann jedoch so angepasst +werden, dass sie in den Arbeisspeicher passt und somit das Generieren stark +verschnellert. Mit genügend Arbeitsspeicher ist der Fehler auch +vernachlässigbar. + +\subsection{Beschleunigung der Generierung} +Es existieren mehere Möglichkeiten das Generierung der Punkte zu verschnellern. + +Eine gute Möglichkeit ist die Nutzung von mehr Rechenleistung. Bei der Nutzung +von \( n \) Rechenkernen ist das Generieren von Sternen \( n \) mal schneller. +Die Server des Server-Hosters Hetzner können dabei gut verwendet werden: +Es wird stündlich aberechnet und 32 Kerne mit 128 GB RAM kosten \( \approx \) +50ct / h was es ermöglicht für einen vergleichsweisen Günstigen Preis, sehr +viele Koordinates zu generieren. + +Die Ausgabe von jeder Potentiellen Koordinate in die Kommandozeile verlangsamt +die Generierung unglaublich stark, da der Rechner darauf wartet das die Ausgabe +fertig ist bevor er mit der nächsten rechnung beginnt was zu einer relativ +starken verlangsamung der Generierung führt. + +\section{Simulieren} + +\subsection{Die Entstehung von Galaxien} +``Eine Galaxie ist eine durch gravitation gebundene große Ansammlung von +Sternen, Planetensystemen, Gasnebeln und sonstigen Stellaren Objekten.`` +\footnote{ https://de.wikipedia.org/wiki/Galaxie} + +Demnach ist es relativ Einfach eine Galaxie zu generieren: es werden einfach +ganz viele Objekte in einen Raum geworfen. Das reicht jedoch nicht um die +Objekte als Galaxie definieren zu können, da sie nicht ``durch Gravitation +gebunden`` sind. + +Um dies zu tun muss die Kraft zwischen allen Objekten in der Galaxie berechnet +werden und damit die Position des Objektes nach einer bestimmten Zeit bestimmt +werden. + +Dies reicht jedoch auch nicht um eine ``stabile`` Galaxie zu generieren: +berechnet man nur die Kräfte die auf ruhende Objete in einem Reibungfreiem Raum +wirken, würden alle Objekte zum Massemittelpunkt gezugen werden und die Galaxie +würde somit implodieren. Es ist also nötig auf die Sterne in der Galaxie +anfangskräfte auszuwirken. Diese Kräfte sind durch die Rotation der Galaxie um +den Massemittelpunkt der Galaxie definiert, man rotiert also die Galaxie und +gleicht dadurch die Kraft die Alle Sterne richtung Massemittelpunkt zieht aus. +Rotiert man die Galaxie jedoch zu schnell, explodiert sie Förmlich, da die +Sterne nicht mehr zusammengehalten werden und die Fliehkraft sie einfach +auseinanderzieht. + +\subsection{Berechnung der Beschleunigungen} +Um die Beschleunigung die auf einen Stern wirk zu berechnen wird folgendes +berechnet: + +\begin{equation} \label{eq:beschleunigung} + a = G \cdot \frac{\Delta{M_2}}{\Delta{r}^2} +\end{equation} + +\( G \) steht hier fúr die Universellt Gravitaionskraft, \( \Delta M \) für die +Masse des Objektes das Umkresit wird und \( \Delta r \) für die Entfernung zum +Mittelpunkt des Objektes das umkreist wird. +Problem ist, dass kein Objekt umkreist wird sondern eine große Anzahl an Sternen. +Es ist also nich möglich mithilfe von herkömmlichen Methoden die Beschleunigung +die auf einen Stern wirkt zu berechnen. + +\subsubsection{Die Kraft als Vektor} +Um die Kraft als Vektor darkzustellen, muss die Formel \ref{eq:beschleunigung} +mithilfe von Vektoren neu aufgestellt werden: + +\begin{equation} \vec{F}_{12} = \underbrace{-G \frac{m_1 m_2}{|r_{12}|^2}}_{Scalar} +\cdot \underbrace{\frac{r_2 - r_1}{|r_2 - r_1|}}_{Vector} \end{equation} + +Die Summe der Kräfte die auf einen Stern wirken ist somit die Summe aller +Kräfte die zwischen dem jeweiligen Stern \( a \) und allen anderen Sternen +wirken: + +\begin{equation} F_{a} = \sum_{i=0}^{n-1} F_{ai} \end{equation} + +\subsubsection{Probleme} +Ein Problem das auftritt wenn die Kräfte zwischen allen Sternen berechnet +werden ist, dass der Rechenaufwand \( O(n \cdot n-1) \approx O(n^2) \) beträgt. +Problematisch wird es, wenn der mittlere Fehler, der bei der Berechnung der +Kraft entsteht, größer als die Kraft wird. Das passier bei Sternen die sehr +weit von einander entfernt liegen. Statt weiterzurechnen kann man die Sterne +dann einfach weglassen, da die Daten unzuverlässig sin. + +Die Lösung des Problems ist die verwendung des Barnes-Hut Algorithmuses, der +duch die Unterteilung der Galaxie in verschiden große Zellen die +Rechenkomplexität von \( O(n^2) \) auf \( O(n \log(n) \) runterbricht: + +\subsubsection{Berechnung der Umlaufgeschwindigkeit} +Die Umlaufgeschwindigket kann berechnet werden, indem die Kraft die die Sterne +in die Mitte der Galaxie zieht \( \left( F = G \cdot \frac{m \cdot M}{r^2} +\right) \) mit der Zentripetalkraft \( \left( F_z = \frac{m \cdot v^2}{r} +\right)\) gleichgesetzt wird: + +\begin{equation} +v = \sqrt{\frac{G \cdot M_E}{r}} +\end{equation} + +\( M_E \) steht dabei für die Masse der Erde, \( G \) für die +Gravitaitonskonstante und \( r \) für den Bahnradius. Da wir jedoch nicht in +der Erdumlaufbahn, sondern in einer Galaxienumlaufbahn hantieren, können wir +nicht die Masse der Erde nutzen. Wir müssen daher eine andere Möglichkeit +nutzen, die größe der Masse, die den Stern in Richtung Massemittelpunkt zieht zu +berechnen. + +\subsubsection{Ellipsen und die Geschwindigkeit der Sterne} +Da die Sterne nicht auf perfekten Kreisbahnen um den Mittelpunkt der Galaxie +fliegen muss in betracht gezogen werden wie die Sterne auf Elliptischen Bahnen +orbitieren. Wichtigt ist dabei die Geschwindigkeit, diese muss zwischen der +ersten Kosmischen Geschwindigkeit \( v_k \) und der zweiten Kosmischen +Geschwindigkeit \( v_P \) liegen. Die beiden Kosmischen Geschwindigkeiten sind +folgendermaßen definiert: + +\begin{equation} +v_{k1} = \sqrt{\frac{GM}{r}} +\end{equation} +\begin{equation} +v_{k2} = \sqrt{\frac{2GM}{r}} +\end{equation} + +Die Tatsache das die Sterne auf Elliptischen Bahnen unterwegs sind ist für die +Berechnung irrelevant, da eh für jeden Zeitschritt \( t \) eine neue Kraft +berechnet wird aus der eine Beschleunigung berechnet wird die wiederum die neue +Position des Sternes ergibt. Hält man die Geschwindigkeit der Sterne somit im +interval \( (v_{k1} ; v_{k2}) \), dann ergibt sich (in der Therorie) von +alleine eine elliptische Bahn. + +\subsection{Entwicklung der nötigen Software} +Die Software ist komplett in Golang geschrieben was die nutzung von mehreren +Threads mithilfe von Go-Methoden stark vereinfacht. Um den Barnes-Hut +Algorithmus anzuwenden muss die Galaxie in einen Octree unterteilt werden. +Dabei wird eine Zelle definiert die alle Sterne beinhaltet welche anschließen +solange unterteilt, bis eine der drei Endbedingungen eintrifft: \begin{itemize} + \item Die Zelle enthält weniger als eine vordefinierte mindestmenge an + Sternen \item Die Zelle ist kleiner als eine vordefinierte +mindestgröße \item Es wurde eine maximale Anzahl an Unterteilungen vorgenommen +\end{itemize} Ein wichtiger Aspekt ist jedoch auch, dass die Zellen rekursiv +generiert werden. Kurzgesagt, die 'kinder'-Zellen dürfen müssen aus der +Koordinates der 'Eltern'-Zellen generiert werden. Ist eine die übergeordnete +Zell beispielweise definiert durch ihren Mittelpunkt \( m \) und die Maximale +Breite \( b \) des Feldes, kann die Position der jeweiligen untergeordneten Zelle +folgendermaßen berechnet werden: + + +\begin{equation} + NW = \left( m \pm \frac{b}{2}, m \pm \frac{b}{2} \right) +\end{equation} + + +\bigskip + +\begin{center} +\begin{tikzpicture} + % First Layer + \draw [line width=0.5mm] (0, 0) rectangle (6, 6); + + % Second Layer + \draw [line width=0.25mm] (0, 0) rectangle (3, 3); + \draw [line width=0.25mm] (3, 0) rectangle (6, 3) node[pos=0.5] { \( \delta \) }; + \draw [line width=0.25mm] (0, 3) rectangle (3, 6) node[pos=0.5] { \( \alpha \) }; + \draw [line width=0.25mm] (3, 3) rectangle (6, 6) node[pos=0.5] { \( \beta \) }; + + % Third Layer + \draw [line width=0.125mm] (0, 0) rectangle (1.5, 1.5) node[pos=0.5] { \( \gamma \gamma \) }; + \draw [line width=0.125mm] (1.5, 0) rectangle (3, 1.5) node[pos=0.5] { \( \gamma \delta \) }; + \draw [line width=0.125mm] (0, 1.5) rectangle (1.5, 3) node[pos=0.5] { \( \gamma \alpha \) }; + \draw [line width=0.125mm] (1.5, 1.5) rectangle (3, 3) node[pos=0.5] { \( \gamma \beta \) }; +\end{tikzpicture} +\end{center} + +Nehmen wir als Beispiel das Feld \( \gamma \beta \). + +\subsubsection{Barnes-Hut-simulation} +Wie bereits beschrieben wird die Galaxie in Zellen unterteilt. Dabei kann, wenn +eine Zelle weit genug von einem spezifischen Stern entfernt ist, die Zelle zu +ihrem Massemittelpunkt vereinfacht werden. Der Massemittelpunkt kann wiefolgt +berechnet werden: + +\begin{equation} +\left( \frac{ \sum_{i=0}^{n} x_i \cdot m_i }{ \sum_{i=0}^{n} m}, +\frac{ \sum_{i=0}^{n} y_i \cdot m_i }{ \sum_{i=0}^{n} m } \right) +\end{equation} + +Dabei wird die mithilfe ihrer Masse gewichtete Summe der Sterne durch die +gesamt Masse geteilt um die geweilige Coordinaten-komponente zu erhalten. Dies +muss für jede Zelle einmal getan werden und in der jeweiligen Zellen-struktur +gespeichert werden wodurch am Ende jede Zelle die Koordinaten ihres +Massemittelpunktes kennt. + +Der Barnes-Hut-Algorithmus verringert die Anzahl zu berechnenden Kräfte durch +geeignetes Zusammenfassen von Teilchengruppen zu Pseudoteilchen +\footnote{https://de.wikipedia.org/wiki/Barnes-Hut-Algorithmus}. + +Der um eine Abschätzung zu bekommen, wie gut es ist, die Sterne zu bündeln, +muss darauf geachtet werden, das das Verhältnis vom Gruppendurchmesser \( d \) +zum Radius \( r \) möglichst gering ist: + +\begin{equation} \label{theta} \theta = \frac{d}{r} \end{equation} + +Die Datenstruktur die einen Barnes-Hut Baum speichert ist am besten wiefolgt +definiert: + +\subsubsection{Datentypen} +Um generell irgendwas zu tun muss in fast allen fällen etwas definiert werden. +Zur Simulation von Galaxien brauchen wir voallem eine Methode, Sterne +einheitlich zu definieren. Der unten definierte Vec2-typ kann einen Vektor oder +eine Koordinate darstellen was ihn in der Anwendung zu einem praktischen +Hilfsmittel macht. Er speichert die X und Y Komponente der jeweiligen Struktur +die er darstellen soll als float64-typ. + +\begin{lstlisting} +type Vec2 struct { + X float64 + Y float64 +} +\end{lstlisting} + +Mithilfe des Vec2-typens kann ein Kompletter Stern definiert werden. Dabei wird +ein Stern mithilfe seine Position \( C \), seiner Geschwindigkeit \( V \), und +seiner Masse \( M \) beschrieben. + +\begin{lstlisting} +type Star2D struct { + C Vec2 + V Vec2 + Mass float64 +} +\end{lstlisting} + +Um einen sogennanten quadtree bzw. octree aufzubauen wird erstmal eine +Räumliche Begrenzung benötigt, die einem Raum beschriebt indem die Sterne +enthalten sind oder nicht. Diese grenze ist als `Boundary` definiert, es wird +dabei der Mittelpunkt der Begrenzung und die kürzeste Entfernung zwischen +mittelpunkt und äußerer Begrenzung genutzt um den Raum zu definieren. + +\begin{lstlisting} +type Boundary struct { + Center Vec2 + HalfDimension float64 +} +\end{lstlisting} + +Der eigentliche QuadTree bzw. Octree beinhaltet einige Informationen: Die +Anzahl in ihm enthaltene Sterne, die Räumliche ausbreitung, die eigentlichen +Sterne als Star2D definiert und die RecursionTiefe als integer. Die Definition +des QuadTrees der Unten zu sehen ist enthält Zeiger zu den Kindern des +Quadtrees und ist somit rekusriv definiert was es einfach macht neue Kinder zu +erstellen, da diese eine Kopie ihere Eltern mit einer anderen Begrenzung +darstellen wodurch die in ihnen enthaltenen Sterne weniger werden. + +\begin{lstlisting} +type QuadTree struct { + StarCount int + Boundary Boundary + Star []Vec2 + + NorthWest *QuadTree + NorthEast *QuadTree + SouthWest *QuadTree + SouthEast *QuadTree + + ReccursionDepth int +} +\end{lstlisting} + +\paragraph{Idee:} +Wenn man bei herrausfinden welcher Stern in welcher Zelle liegt jedem Stern +eine Zellen-id zuweist, kann man wenn man die Kraft zwischen zwei sehr weit +entfernten Sternen berechnen will direkt dazu übergehen, die Kraft zum +Massemittelpunkt der Zelle indem der weit eintferne Stern liegt zu berechnen. + +\subsubsection{Runge-Kutta methods} +Die Runge-Kutta Methode wird genutzt, um die Position eines objektes nach einer +Beliebigen Zeit zu approximieren. Dabei kann, bei nutzung eines mglich kleinen +Zeitschrittes, ein sehr genaues Ergebniss erzielt werden. In unserem Fall +haben wir einen Stern auf den eine Kraft wirkt. Wir wollen die Position des +Sternens nach einem Zeitschritt berechnen, jedoch auch eine andere Kraft +miteinbringen um die Sterne auf eine Ellipische Bahn um die Mitte der Galaxie +zu bringen. +Die Geschwindigkeit die der Stern dabei annnimmt kann mit der fogenden Formel +berechnet werden: + +\begin{equation} + v = \sqrt{ar} +\end{equation} + +\subsubsection{Goroutines} +Die nutzung von mehreren sogennanten Go-Methoden ist unglaublich effektiv, da +es die Zeit die gebraucht wird das Programm auszuführen drastisch verringert. +Die implementation ist ebenfalls unglaublich einfach, es recht + +\section{Ergebnisse} +Wie bewertest Du Deine Ergebnisse? Wie passt das zu dem, was Du über Dein Thema +gelesen oder gehört hast? Was ist gut gelaufen im Projekt, was war schlecht, +was könnte noch verbessert werden? Das simulieren von Galaxien ist komplett +ohne optimierungen ein sehr rechenaufwendiger prozess, weshalb einer der +wichtigsten aspekte des Projektes war, die effizienz zu erhöhen. + +\subsection{Das n-Körper Problem} +Das N-Körper Problem ist blöd (aber notwendig D:) (Und es ermöglicht das ganze +erst!) + +\subsection{Beschleunigung der Berechnung von Kräften} +\( n^2 \rightarrow n \cdot log(n) \) +iasd + +\subsection{Fazit} +Welche Antwort kannst Du auf Deine Forschungsfrage geben? Hast Du Dein Ziel +erreicht? Langsam, Ok, schneller, Schnell, Hyperspeed! + + +\section{Quellen und Literaturverzeichnis} + +THE INTERNET! + +\end{multicols*} + +\end{document} + |
