diff options
Diffstat (limited to 'docs')
| -rw-r--r-- | docs/darstellung.tex | 2 | ||||
| -rw-r--r-- | docs/einleitung.tex | 14 | ||||
| -rw-r--r-- | docs/ergebnisse.tex | 15 | ||||
| -rw-r--r-- | docs/fazit.tex | 4 | ||||
| -rw-r--r-- | docs/generieren.tex | 179 | ||||
| -rw-r--r-- | docs/quellenliteraturverzeichniss.tex | 3 | ||||
| -rw-r--r-- | docs/simulieren.tex | 345 | ||||
| -rw-r--r-- | docs/titleabstract.tex | 28 | ||||
| -rw-r--r-- | docs/vektoren.tex | 14 | ||||
| -rw-r--r-- | docs/vorgehensweise.tex | 7 |
10 files changed, 611 insertions, 0 deletions
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. |
