diff options
28 files changed, 646 insertions, 443 deletions
diff --git a/README.md b/README.md index 3952132..fb74e5c 100644 --- a/README.md +++ b/README.md @@ -1,3 +1,9 @@ # Langfassung -Langfassung (Für Jugend Forscht) \ No newline at end of file +Langfassung (Für Jugend Forscht) + +## Special Packages + +| Name | Link | +| --- | --- | +| forest | https://www.ctan.org/pkg/forest | diff --git a/build-d8d5fa6e4473a13034cd240c2aba1bc3845717b292b2bbe431af65003398ec23/main.pdf b/build-d8d5fa6e4473a13034cd240c2aba1bc3845717b292b2bbe431af65003398ec23/main.pdf new file mode 100644 index 0000000..0b4c269 --- /dev/null +++ b/build-d8d5fa6e4473a13034cd240c2aba1bc3845717b292b2bbe431af65003398ec23/main.pdf Binary files differdiff --git a/build-e87dbcfbc8fbfcc24e369e3574cecd348f4c441547d419a7d2d896682105305f/main.pdf b/build-e87dbcfbc8fbfcc24e369e3574cecd348f4c441547d419a7d2d896682105305f/main.pdf new file mode 100644 index 0000000..dc1595c --- /dev/null +++ b/build-e87dbcfbc8fbfcc24e369e3574cecd348f4c441547d419a7d2d896682105305f/main.pdf Binary files differdiff --git a/build-f51847f6d240a73d51e28c92b3fdafb41025b72c15aacd77577b2a4b68f1cdd2/main.pdf b/build-f51847f6d240a73d51e28c92b3fdafb41025b72c15aacd77577b2a4b68f1cdd2/main.pdf new file mode 100644 index 0000000..9c71c36 --- /dev/null +++ b/build-f51847f6d240a73d51e28c92b3fdafb41025b72c15aacd77577b2a4b68f1cdd2/main.pdf Binary files differdiff --git a/current-build b/current-build index d1c0380..5cdc7a6 120000 --- a/current-build +++ b/current-build @@ -1 +1 @@ -build-6169b05f2ba5c683b05359bdd6b2c56e8e2028d67d416a296bfbef08f0775ee9 \ No newline at end of file +build-e87dbcfbc8fbfcc24e369e3574cecd348f4c441547d419a7d2d896682105305f \ No newline at end of file diff --git a/docs/darstellung.tex b/docs/darstellung.tex new file mode 100644 index 0000000..e650479 --- /dev/null +++ b/docs/darstellung.tex @@ -0,0 +1,2 @@ +\section{Darstellung} + diff --git a/docs/einleitung.tex b/docs/einleitung.tex new file mode 100644 index 0000000..48f8539 --- /dev/null +++ b/docs/einleitung.tex @@ -0,0 +1,14 @@ +\section{Einleitung} +Das Projekt ist nach meinem vorletzten Jugend-Forscht Projekt entstanden: Ich +habe ein Praktikum in Astronomischen Rechen Institut in Heidelberg genutzt, um +mit einem Doktoranden\footnote{Tim Tugendhat} das Navarro-Frenk-White Profil, +das zum generieren von Punkt Wolken genutzt wird, zu visualisieren. 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 Ergebnis ist sehr schön: Durch die Nutzung der Programmiersprache Go +war das einbauen der Nutzung von mehreren Threads vergleichsweise einfach. + diff --git a/docs/ergebnisse.tex b/docs/ergebnisse.tex new file mode 100644 index 0000000..9205085 --- /dev/null +++ b/docs/ergebnisse.tex @@ -0,0 +1,15 @@ +\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 + diff --git a/docs/fazit.tex b/docs/fazit.tex new file mode 100644 index 0000000..ec810a6 --- /dev/null +++ b/docs/fazit.tex @@ -0,0 +1,4 @@ +\subsection{Fazit} +Welche Antwort kannst Du auf Deine Forschungsfrage geben? Hast Du Dein Ziel +erreicht? Langsam, Ok, schneller, Schnell, Hyperspeed! + diff --git a/docs/generieren.tex b/docs/generieren.tex new file mode 100644 index 0000000..5fa9294 --- /dev/null +++ b/docs/generieren.tex @@ -0,0 +1,179 @@ +\section{Generieren} + +Das Generieren der Statischen Punkt Wolke 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 das genutzt wird, um +die Räumliche Massen Verteilung von dunkler Materie anhand von Halos die in +N-Körper Simulationen simuliert wurden, zu generieren. Das NFW-Profil kann +jedoch auch genutzt werden um die Massen Verteilung von Sternen darzustellen. +Das Profil generiert für einen gegebenen Abstand \( r \) zum Mittelpunkt der +Galaxie eine Wahrscheinlichkeit \( \rho \). Die Funktion sieht dabei wie folgt aus: +NFW + +\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*} + +Es kann nun mithilfe der Random-Sampling Methode (\ref{subsec:random_sampling}) +ermittelt werden, ob ein Stern beibehalten wird oder nicht. + +\par Möchte man nun herausfinden wie weit ein Punkt mit der Koordinate \( +(x_{1}, x_{2}, x_{3} \) vom Mittelpunkt des Raumes entfernt ist, kann der Satz +des Pythagoras (\ref{eq:pythagoras}) verwendet werden. + +\begin{equation} \label{eq:pythagoras} + r_{3} = \sqrt{x_{1}^{2} + x_{2}^{2} + x_{3}^{2} } +\end{equation} + +Der Abstand \( r_{3} \) zum Mittelpunkt des Raumes kann nun in das NFW-Profil +(\ref{eq:NFW_profile}) gegeben werden um einen Wert \( s \) zu ermitteln welcher +beim Random Sampling verwendet wird: + +\begin{equation} +\rho_{NFW}(r) = \dots = s +\end{equation} + +Dieser Wert \( s \) stellt die Wahrscheinlichkeit dar, das ein Stern der +eine Entfernung \( r \) vom Mittelpunkt der Galaxie besitzt existiert. + +Die Galaxie sieht aus der Ferne jetzt jedoch aus wie ein Würfel, da die aus \( +\rho_{NFW_{1}} \) resultierende Kurve abrupt endet. Dies kann gelöst werden, +indem statt \( \rho_{NFW_{1}}(r) \) folgendes gerechnet wird: \( +\rho_{NFW_{1}}(r) - \rho_{NFW_{1}}(r_{max}) = \rho_{NFW_{2}}(r)\) + +\paragraph{Veranschaulichung:}~\\ + +\begin{center} + \begin{tikzpicture} + \draw[very thin, color=lightgray, step=5mm] (-0.9, -0.9) grid (3.9, 2.4); + \draw[->] (-1,0) -- (4,0) node[right] {$x$}; + \draw[->] (0,-1) -- (0,2.5) node[above] {$y$}; + \draw[scale=0.5, domain=0.25:6.5, smooth, variable=\x, black] plot ({\x},{(1/\x) + 1}) node[above] {$\rho_{NFW_{1}}(x)$}; + \draw[scale=0.5, domain=0.25:6.5, smooth, variable=\x, black] plot ({\x},{1/\x}) node[below] {$\rho_{NFW_{2}}(x)$}; + \end{tikzpicture} +\end{center} + +Problematisch ist hierbei die Tatsache, dass aufgrund der Verschiebung die +Anzahl der Sterne die in Relation zu dem Bereich in dem sie generiert werden +sehr stark sinkt. + +\subsection{Random Sampling} \label{subsec:random_sampling} +\begin{equation}\label{range:psi} + \psi = [ \rho(r_{min}); \rho(r_{max}) ] +\end{equation} + +Sei \( s \) ein zufälliger Wert im Intervall \( \psi \). 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. + +\paragraph{Veranschaulichung:}~\\ + +\begin{center} + \begin{tikzpicture} + % draw the background grid + \draw[very thin, color=lightgray, step=5mm] (-0.9, -0.9) grid (3.9, 2.4); + + % draw the x-ticks + \draw[xshift=0cm](0.5cm, 1pt) -- (0.5cm, -3pt) node[anchor=north] {$r_{1}$}; + \draw[xshift=0cm](1.5cm, 1pt) -- (1.5cm, -3pt) node[anchor=north] {$r_{2}$}; + + % draw the y-ticks + \draw[yshift=0cm](1pt, 0.5cm) -- (-3pt, 0.5cm) node[anchor=east] {$p(r_{1})$}; + \draw[yshift=0cm](1pt, 1.0cm) -- (-3pt, 1.0cm) node[anchor=east] {$p(r_{2})$}; + + % draw the dotted lines connecting the point s_1 + \draw[thick, dotted] (0.5, 0) -- (0.5, 0.5); + \draw[thick, dotted] (0, 0.5) -- (0.5, 0.5); + + % draw the dotted lines connecting the point s_2 + \draw[thick, dotted] (0, 1.0) -- (1.5, 1.0); + \draw[thick, dotted] (1.5, 0) -- (1.5, 1.0); + + % draw the axes + \draw[->] (-1,0) -- (4,0) node[right] {$r$}; + \draw[->] (0,-1) -- (0,2.5) node[above] {$\psi$}; + + % draw the plot + \draw[scale=0.5, domain=0.25:6.5, smooth, variable=\x, black] + plot ({\x},{(1/\x) + 1}) node[above] {$\rho_{NFW_{1}}(x)$}; + + % draw the points + \fill (0.5, 0.5) circle (0.05) node[above] {$s_1$}; + \fill (1.5, 1) circle (0.05) node[above] {$s_2$}; + \end{tikzpicture} +\end{center} + +In der obigen Abbildung ist zu sehen wir zwei zufällige Punkte \( s_1 \) und \( s_2 \) +generiert wurden. + +Angenommen es wurde ein Stern generiert für den nach Formel +(\ref{eq:pythagoras}) gilt: \( r = \sqrt{x_{1}^{2} + x_{2}^{2} + x_{3}^{2}} = +\dots = r_1 \). Es wird dann ein Zufälliger Wert \( p(r_2) \) im in +(\ref{range:psi}) definierten Intervall generiert. Die folgenden zwei Fälle +können dann eintreten und werden wie in (\ref{cases:random_sampling}) +abgehandelt. + +\kern-1em + +\begin{equation}\label{cases:random_sampling} +\begin{cases} +s_1 \leq NFW(r_1) & \rightarrow \text{Stern wird beibehalten}\\ +s_1 > NFW(r_1) & \rightarrow \text{Stern wird verworfen} +\end{cases} +\end{equation} + + +\subsection{Lookup Tabellen} +Statt nun für jeden Stern die Distanz des jeweiligen Sternes \( r \) in das +NFW-Profil (\ref{eq:NFW_profile}) einzusetzen, kann das NFW-Profil im vorhinein +berechnet werden. Es wird dabei eine Tabelle erstellt in der die Entfernung des +Sternes zum Mittelpunkt der Galaxie der jeweiligen Wahrscheinlichkeit +zugeordnet wird: + +\begin{center} +\begin{tabular} {l | l} + \( r_n \quad n \in \mathbb{N} \) & \( \rho_n \quad n \in \mathbb{N} \) \\ \hline\hline + \( r_1 \) & \( \rho_1 \) \\ \hline + \( r_2 \) & \( \rho_2 \) \\ \hline + \( r_3 \) & \( \rho_3 \) \\ \hline + \( \dots \) & \( \dots \) \\ \hline + \( r_n \) & \( \rho_n \) \\ +\end{tabular} +\end{center} + +Die Tabelle kann jedoch nicht so genaue Ergebnisse liefern wie das NFW-Profil, +sie kann jedoch so angepasst werden, dass sie in den Arbeitsspeicher passt und +somit das NFW-Profil so genau wie möglich widerspiegelt und das Generieren +stark verbessert. Mit genügend Arbeitsspeicher ist der Fehler dann auch +vernachlässigbar. Ein Kritischer Faktor, der beachtet werden muss wenn +Lookuptabellen genutzt werden, ist die Geschwindigkeit des jeweiligen +Speichermediums. Nutzt man z.B. Eine sehr langsame Festplatte kann es mehr +Sinne machen die jeweiligen Werte direkt zu berechnen. Dagegen ist eine +schnelle SSD (Solid-State-Drive) um einiges schneller. + +TODO: Versuchsreihe. + +\subsection{Beschleunigung der Generierung} +Es existieren mehrere Möglichkeiten die Generierung der Punkte zu verbessern. + +Eine gute Möglichkeit ist die Nutzung von mehr Rechenleistung. Bei der Nutzung +von \( n \) mal sovielen Rechen kernen ist das Generieren von Sternen \( n \) +mal schneller. Die Server des Server-Hosters Hetzner können dabei gut +verwendet werden: Es wird stündlich abgerechnet und 32 Kerne mit 128 GB RAM +kosten \( \approx \) 50ct/h was es ermöglicht für einen vergleichsweisen +Günstigen Preis, sehr viele Koordinaten 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. diff --git a/docs/quellenliteraturverzeichniss.tex b/docs/quellenliteraturverzeichniss.tex new file mode 100644 index 0000000..43b1f9b --- /dev/null +++ b/docs/quellenliteraturverzeichniss.tex @@ -0,0 +1,3 @@ +\section{Quellen und Literaturverzeichnis} + +THE INTERNET! diff --git a/docs/simulieren.tex b/docs/simulieren.tex new file mode 100644 index 0000000..fa737b0 --- /dev/null +++ b/docs/simulieren.tex @@ -0,0 +1,345 @@ +\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{\url{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 um damit die Position der jeweiligen Objekte nach einer bestimmten Zeit +bestimmen zu können. + +Dies reicht jedoch auch nicht um eine ``stabile`` Galaxie zu generieren: +berechnet man nur die Kräfte die auf ruhende Objekte in einem Reibungsfreiem Raum +wirken, würden alle Objekte zum Massenmittelpunkt gezogen werden und die Galaxie +würde somit implodieren. Es ist also nötig auf die Sterne in der Galaxie +Anfangs Kräfte zu wirken. Diese Kräfte sind durch die Rotation der Galaxie um +den Massenmittelpunkt der Galaxie definiert, man rotiert also die Galaxie und +gleicht durch die Zentripetalkraft, die Kraft die Alle Sterne Richtung +Massenmittelpunkt 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 wirkt 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 Universelle Gravitationskraft, \( \Delta M \) für die +Masse des Objektes das Umkreist 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 nicht möglich mithilfe von herkömmlichen Methoden die Beschleunigung +die auf einen Stern wirkt zu berechnen. + +TODO: und jetzt? + +\subsubsection{Die Kraft als Vektor} +Um die Kraft als Vektor darzustellen, muss die Formel \ref{eq:beschleunigung} +mithilfe von Vektoren wiefolgt 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{Berechnung der Umlaufgeschwindigkeit} +Die Umlaufgeschwindigkeit 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 +Gravitationskonstante und \( r \) für den Bahn Radius. Da wir jedoch nicht in +der Erdumlaufbahn, sondern in einer Galaxien Umlaufbahn 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 Massenmittelpunkt 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. + +\subsubsection{Zu lösende 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. + +Es kommt zu Problemen, wen nder mittlere Fehler, der bei der Berchnung der Kraft +entsteht größer als die wirkende Kraft wird. Dies passiert unter anderem dann, +wenn der Abstand zwischen den Sternen so groß wird, das die wirkende Kraft so gering ist +das sie mithilfe von Computern nichtmehr sinvoll dargestellt wird. +Statt nun mit Rundungsfehlen zu rechnen, können diese Sterne, die sehr weit enfrent vom +Stern dessen kräfte berechnet werden sollen, einfach nicht mehr beachtet werden, +da sie nicht sinvoll beitragen. +Um dieses Problem zu lösen wird der Barnes-Hut Algorithmus verwenden. Dieser Algorithmus +unterteil einen Bereich in variabel große Zellen und mindert die Laufzeit von \( O(n^2) \) auf +\( O(n \log(n) \). + +\subsubsection{Generierung von Quadtrees und die nutzung des Barnes-Hut +Algorithmus\footnote{http://arborjs.org/docs/barnes-hut}} + + +\begin{equation} + NW = \left( m \pm \frac{b}{2}, m \pm \frac{b}{2} \right) +\end{equation} + + +\bigskip + +\begin{minipage}{0.45\textwidth} +\begin{tikzpicture}[level 1/.style={level distance=1.5cm}] + % 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); + \draw [line width=0.25mm] (0, 3) rectangle (3, 6); + \draw [line width=0.25mm] (3, 3) rectangle (6, 6); + + % Third Layer (South West) + \draw [line width=0.125mm] (0, 0) rectangle (1.5, 1.5); + \draw [line width=0.125mm] (1.5, 1.5) rectangle (3, 3); + + % Third Layer (North East) + \draw [line width=0.125mm] (3, 3) rectangle (4.5, 4.5); + \draw [line width=0.125mm] (4.5, 4.5) rectangle (6, 6); + + % Forth Layer (North West) + \draw [line width=0.125mm] (3, 4.5) rectangle (3.75, 5.25); + \draw [line width=0.125mm] (3.75, 5.25) rectangle (4.5, 6); + + % Draw the nodes + \node at (1, 4.5) {$A$}; + \node at (4, 5.5) {$B$}; + \node at (3.5, 5) {$C$}; + \node at (5, 4) {$D$}; + \node at (2.75, 2.75) {$E$}; + \node at (0.75, 0.75) {$F$}; + \node at (2, 0.75) {$G$}; + \node at (3.5, 0.75) {$H$}; +\end{tikzpicture} +\end{minipage} + +\begin{forest} + for tree={circle,draw, s sep+=0.25em} + [ + [A] + [ + [ + [] + [B] + [C] + [] + ] + [] + [] + [D] + ] + [ + [] + [E] + [F] + [G] + ] + [H] + ] +\end{forest} + +Um die Kraft die auf einen bestimmten Stern wirkt zu berechnen, wird der Baum +von der Wurzel aus nach unten durchlaufen. Beispiel: Berechnung der Kraft die +auf den Stern A wirkt. Der 'Quadtree' wird von oben nach unten durchgegangen, +also wird das Verhältnis zwischen der Entfernung des Massemittelpunktes zu dem +Stern A (\(\approx 42\)) und der Breite der jeweiligen Zelle (100) berechnet +(Formel \ref{eq:barnes_hut}): \( \frac{100}{43} \not> \theta = 0.5\). + +\begin{equation} \label{eq:barnes_hut} \theta = \frac{d}{r} \end{equation} + +Ist das Verhältnis größer als ein im vorhinein definierter Grenzwert \( \theta +\), dann wird weiter in den Quadtree ineingegangen und eine Ebene tiefer +rekursiv weitergeprüft. + +Die Koordinate des Massemittelpunktes \( \varsigma \) des jeweiligen Knotens +kann wie in Formel (\ref{eq:mean_mass}) beschrieben berechnet werden: + +\begin{equation} \label{eq:mean_mass} +\varsigma = \left( \dfrac{ \displaystyle \sum_{i=0}^{n} x_i \cdot m_i }{ +\displaystyle \sum_{i=0}^{n} m_i } , \frac{ \displaystyle \sum_{i=0}^{n} y_i +\cdot m_i }{ \displaystyle \sum_{i=0}^{n} m_i } \right) +\end{equation} + +Es ist somit durch \( \theta \) eine Endbedingung gegeben, welche verhindert +das zu weit in den Baum vorgedrungen wird und somit auch verhindert, dass +Sterne die in einer zu großen Entfernung zu dem ursprungssten liegen und dicht +genug grupiert sind zusammengefasst werden. + +\subsubsection{Implementierung des Quadtrees} +Um generell irgendwas zu tun muss in fast allen fällen etwas definiert werden. +Zur Simulation von Galaxien brauchen wir vor allem 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 Vec struct { + X float64 + Y float64 + Z float64 +} + +method (Vec2) insert() {...} +method (Vec2) insideOf() bool {...} +func newVec2() Vec2 {...} +\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 Star struct { + C Vec + V Vec + Mass float64 +} + +method (Vec2) insideOf() bool {...} +\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 Vec + HalfDimension float64 +} + +function newBoundary() {...} +\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 +} +method (QuadTree) insert(Star) bool {...} +method (QuadTree) subdivide() {...} +\end{lstlisting} + +\subsubsection{Benchmarking} + +Um den Geschwindigkeitsvorteil darzustellen, kann die Kraft zwischen \(n\) +homogen verteilten Sternen berechnet werden. Einmal mit der Brute-Force Methode +und einmal mit der im Barnes-Hut Algorithmus beschriebenen Methode. + +%\begin{figure*}[ht!] +%\centering +%\begin{tabular*} {l | l | l | l || l} +% left bound & right bound & step & amount of stars & time \\ +% -5e5 & 5e5 & 5e3 & 40003 & 1m25 \\ +%\end{tabular*} +%\end{figure*} + +\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 + +\subsection{Netwerkfoo} + +Damit das Projekt so gut wie möglich skalliert, wird die Anwendung in mehrere +kleine Dienste aufgeteilt die jeweils eine funktion übernehmen und +untereinander kommunizieren. Dabei läuft jede Anwendung in einem eigenen +Kontainer (siehe \ref{subsubsec:Docker}) und kann somit in falle eines +nadelöhrs mehrfach gestartet werden und über einen reverse-http-proxy (siehe +\ref{subsubsec:Traefik}) mit daten versorgt werden. + +\subsubsection{Die verschiedenen Dienste} +Um die Generierung der Punktwolken und die anschließende Simulation der Wolke +in einzelne Microservices aufzuspalten muss erstmal definiert werden für welche +Dienste es überhaupt sinn macht sie in einzelne instanzen abhängig bzw. +unabhängig von einander agieren. + +\subsubsection{Docker} \label{subsubsec:Docker} +\subsubsection{Docker-compose} +\subsubsection{Traefik} \label{subsubsec:Traefik} +\subsubsection{Kubernetes / Docker swarm} +\subsubsection{grafana} + diff --git a/docs/titleabstract.tex b/docs/titleabstract.tex new file mode 100644 index 0000000..855ab15 --- /dev/null +++ b/docs/titleabstract.tex @@ -0,0 +1,28 @@ +% title +\title{\huge Galaxy Simulation\\ \large Jugend Forscht 2018/2019} +\date{2018 - 2019} +\author{\Large{Emile Hansmaennel}\\ Theodor-Fliedner-Gymnasium, Heinrich Heine +Universität Düsseldorf} + +% title with an abstract in a single column +\twocolumn[ + \maketitle + \centering + \begin{minipage}{0.7\textwidth} +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. + \end{minipage} + \bigskip + \bigskip +] + + + diff --git a/docs/vektoren.tex b/docs/vektoren.tex new file mode 100644 index 0000000..dcc1c4d --- /dev/null +++ b/docs/vektoren.tex @@ -0,0 +1,14 @@ +\section{Vektoren} + +Die Kräfte die auf die jeweiligen Sterne wirken werden mithilfe von Vektoren +dargestellt. Hierbei ist es sinnvoll eine einheitliche Vektor-länge zu +definieren, welche die Richtung der wirkenden Kraft beschreibt. Die Stärke der +Kraft als Gradient definiert, der von blau (schwach) nach rot (stark) verläuft. +Um die Farbe entsprechend der Kraft darzustellen wird die Stärke der wirkenden +Kraft duch eine Sigmoidfunktion geschoben und das Ergebnis in wiefolgt +verwenden: RGB(val, 0, 1-val). + +\begin{equation} +f(x) = \frac{L}{1 + e^{-k(x-x_0)}} +\end{equation} + diff --git a/docs/vorgehensweise.tex b/docs/vorgehensweise.tex new file mode 100644 index 0000000..a790551 --- /dev/null +++ b/docs/vorgehensweise.tex @@ -0,0 +1,7 @@ +\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 Punkt Wolke, 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. diff --git a/last-successful b/last-successful index d1c0380..5cdc7a6 120000 --- a/last-successful +++ b/last-successful @@ -1 +1 @@ -build-6169b05f2ba5c683b05359bdd6b2c56e8e2028d67d416a296bfbef08f0775ee9 \ No newline at end of file +build-e87dbcfbc8fbfcc24e369e3574cecd348f4c441547d419a7d2d896682105305f \ No newline at end of file diff --git a/main.tex b/main.tex index dee760e..b655726 100644 --- a/main.tex +++ b/main.tex @@ -1,21 +1,21 @@ -\documentclass[a4paper, 10pt]{article} +\documentclass[twocolumn, a4paper, 10pt]{article} \usepackage[top=2cm, bottom=2cm, left=1.5cm, right=1.5cm]{geometry} -\usepackage[utf8]{inputenc} +\usepackage[utf8]{inputenc} % support for utf8 chars %\usepackage[english]{babel} -\usepackage[german]{babel} +\usepackage[german]{babel} % german language +% general math stuff \usepackage{amsmath} \usepackage{amsfonts} \usepackage{amsthm} -\usepackage[hidelinks]{hyperref} -\usepackage{graphicx} -\usepackage{caption} -\usepackage{lmodern} -\usepackage{tikz} -\usepackage{multicol} -\usepackage{lipsum} +\usepackage[hidelinks]{hyperref} % clickable links +\usepackage{graphicx} % graphics +\usepackage{caption} % captions +%\usepackage{lmodern} % even nicer font +\usepackage[stable]{footmisc} % footnotes +% code listings \usepackage{listings} \usepackage{listings-golang} @@ -24,440 +24,26 @@ language=golang, } -\linespread{1} +% tikz for drawing stuff and forest for nice graphs +\usepackage{tikz} +\usepackage{forest} -\newcommand{\rarrow}{\( \rightarrow \)} +\linespread{1} \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*} +\input{docs/titleabstract.tex} +\tableofcontents + +\input{docs/einleitung} +\input{docs/vorgehensweise} +\input{docs/generieren} +\input{docs/simulieren} +\input{docs/ergebnisse} +\input{docs/darstellung} +\input{docs/vektoren} +\input{docs/fazit} +\input{docs/quellenliteraturverzeichniss} \end{document} diff --git a/splitup/build-15508d44111824f9ac86d6e447b2c825db8ea809efee6c739185447f33141c39/main1.pdf b/splitup/build-15508d44111824f9ac86d6e447b2c825db8ea809efee6c739185447f33141c39/main1.pdf new file mode 100644 index 0000000..5f05180 --- /dev/null +++ b/splitup/build-15508d44111824f9ac86d6e447b2c825db8ea809efee6c739185447f33141c39/main1.pdf Binary files differdiff --git a/splitup/build-2b05ba314804ef4117eec03241dc8f32a5323b5bdfe67d108cc7730fabe9ab45/main1.pdf b/splitup/build-2b05ba314804ef4117eec03241dc8f32a5323b5bdfe67d108cc7730fabe9ab45/main1.pdf new file mode 100644 index 0000000..4a36d8f --- /dev/null +++ b/splitup/build-2b05ba314804ef4117eec03241dc8f32a5323b5bdfe67d108cc7730fabe9ab45/main1.pdf Binary files differdiff --git a/splitup/build-374418b26e79a132173bb7aa355239387bb2ce9c1eef940e25fabf03fd91c565/main1.pdf b/splitup/build-374418b26e79a132173bb7aa355239387bb2ce9c1eef940e25fabf03fd91c565/main1.pdf new file mode 100644 index 0000000..66b5dcd --- /dev/null +++ b/splitup/build-374418b26e79a132173bb7aa355239387bb2ce9c1eef940e25fabf03fd91c565/main1.pdf Binary files differdiff --git a/splitup/build-69f3e33907221fffc27756f6a1cbc390aded214cd0a70c4fb3db31b616f3f8d3/main1.pdf b/splitup/build-69f3e33907221fffc27756f6a1cbc390aded214cd0a70c4fb3db31b616f3f8d3/main1.pdf new file mode 100644 index 0000000..1f35c9b --- /dev/null +++ b/splitup/build-69f3e33907221fffc27756f6a1cbc390aded214cd0a70c4fb3db31b616f3f8d3/main1.pdf Binary files differdiff --git a/splitup/build-6fcfc948d994eee8f470560e71183f9c9e4bc76acdec9606b7a7ba263f393728/main1.pdf b/splitup/build-6fcfc948d994eee8f470560e71183f9c9e4bc76acdec9606b7a7ba263f393728/main1.pdf new file mode 100644 index 0000000..87c376e --- /dev/null +++ b/splitup/build-6fcfc948d994eee8f470560e71183f9c9e4bc76acdec9606b7a7ba263f393728/main1.pdf Binary files differdiff --git a/splitup/build-7dd73cebd2d9afb118a4a1e3579c7909842ae739ee84205f71b413eb7d2c2917/main1.pdf b/splitup/build-7dd73cebd2d9afb118a4a1e3579c7909842ae739ee84205f71b413eb7d2c2917/main1.pdf new file mode 100644 index 0000000..2b7d6e9 --- /dev/null +++ b/splitup/build-7dd73cebd2d9afb118a4a1e3579c7909842ae739ee84205f71b413eb7d2c2917/main1.pdf Binary files differdiff --git a/splitup/build-8995ade21ded2b3b81949741618d6f5fe5e542bd21bd4d04852fea32145c5033/main1.pdf b/splitup/build-8995ade21ded2b3b81949741618d6f5fe5e542bd21bd4d04852fea32145c5033/main1.pdf new file mode 100644 index 0000000..4fd42a2 --- /dev/null +++ b/splitup/build-8995ade21ded2b3b81949741618d6f5fe5e542bd21bd4d04852fea32145c5033/main1.pdf Binary files differdiff --git a/splitup/build-89b509ecf97cc32034c25f8f2de077272f9f7fdba2db344c32c330601b515955/main1.pdf b/splitup/build-89b509ecf97cc32034c25f8f2de077272f9f7fdba2db344c32c330601b515955/main1.pdf new file mode 100644 index 0000000..edf9faf --- /dev/null +++ b/splitup/build-89b509ecf97cc32034c25f8f2de077272f9f7fdba2db344c32c330601b515955/main1.pdf Binary files differdiff --git a/splitup/build-b5d50c6d25200e05c8f3d7f1278d2fd04686b9a7729691fec9c1c31be8c14592/main1.pdf b/splitup/build-b5d50c6d25200e05c8f3d7f1278d2fd04686b9a7729691fec9c1c31be8c14592/main1.pdf new file mode 100644 index 0000000..4fee570 --- /dev/null +++ b/splitup/build-b5d50c6d25200e05c8f3d7f1278d2fd04686b9a7729691fec9c1c31be8c14592/main1.pdf Binary files differdiff --git a/splitup/build-d5ec6f6238542577ca5bb36d8f27c08758831b991fba55e0f765b6d7461d021c/main1.pdf b/splitup/build-d5ec6f6238542577ca5bb36d8f27c08758831b991fba55e0f765b6d7461d021c/main1.pdf new file mode 100644 index 0000000..8e6e18a --- /dev/null +++ b/splitup/build-d5ec6f6238542577ca5bb36d8f27c08758831b991fba55e0f765b6d7461d021c/main1.pdf Binary files differdiff --git a/splitup/listings-golang b/splitup/listings-golang new file mode 160000 +Subproject f72f1456b57bb6fd27d0ea658fa3e51ea9fc31e |
