save HEAD master

1 files changed, 268 insertions, 0 deletions

diff --git a/.hidden/main.tex b/.hidden/main.tex
new file mode 100644
index 0000000..90496dc
--- /dev/null
+++ b/.hidden/main.tex
@@ -0,0 +1,268 @@
+\documentclass[twocolumn, 10pt]{article}
+
+\usepackage{geometry}
+\geometry{
+	a4paper,
+	total={6.85in, 9.92in},
+	left=0.71in,
+	top=0.63in,
+}
+\usepackage[utf8]{inputenc}
+\usepackage{hyperref}
+\usepackage{listings}
+\usepackage{float}
+\usepackage{tikz}
+\usepackage{forest}
+\usepackage{scrextend}
+
+\usepackage{geometry}
+\geometry{
+a4paper,
+    total={6.85in, 9.92in},
+    left=0.71in,
+    top=0.63in,
+}
+
+
+\pagenumbering{gobble}
+
+\title{Accelerating simulations by clustering bodies using the Barnes-Hut algorithm}
+\author{Page Out!}
+
+\makeatletter
+\newcommand{\fsize}{\f@size pt }
+\newcommand{\textFontName}{\f@family}
+\renewcommand{\maketitle}{
+\begin{flushleft}
+{\noindent\Huge\bf\@title}\break
+\end{flushleft}
+}
+\makeatother
+
+
+\begin{document}
+\twocolumn[
+\maketitle
+]
+
+In a space with \( n \)-bodies, there are \( n-1 \) forces acting on each body.
+When simulating the forces acting on all the bodies, \( n \cdot (n-1) \) forces
+need to be calculated for estimating the new position of the individual bodies.
+With a big enough amount of bodies, this gets problematic. Let's take a real
+galaxy with \( 2 \cdot 10^{8} \) Stars. The total amount of forces that need to
+be calculated are \( 4 \cdot 10^{16} \). The amount of forces that need to be
+calculated can be reduced by utilizing the Barnes-Hut algorithm clustering the
+bodies resulting in much less calculations.
+
+\begin{figure}[H]
+\centering
+    \begin{tikzpicture}
+        \tikzstyle{circlestyle}=[shape=circle,thick,fill,draw, inner sep=0cm]
+        \node at (0, 0) {};
+        \node at (9, 0) {};
+
+        % Random seed for RNG
+        \pgfmathsetseed{7};
+
+        \foreach \x in {1,...,40}
+        {
+          % Find random numbers
+          \pgfmathrandominteger{\a}{10}{390}
+          \pgfmathrandominteger{\b}{10}{390}
+
+          % Scale numbers nicely
+          \pgfmathparse{0.005*\a}\let\a\pgfmathresult;
+          \pgfmathparse{0.005*\b}\let\b\pgfmathresult;
+
+          % draw the circle
+          \fill (\a, \b) circle (0.03);
+        };
+
+        % draw a box around the star cluster
+        \draw[] (0,0) rectangle (2, 2);
+        \node[] at (1, 1) (A1) {};
+        \draw[arrows=<->] (0,-0.2) -- node[midway, align=center, below] {\(d\)} (2,-0.2);
+
+        % draw a star in the far right of the image
+        \node[circlestyle, minimum size=2pt, label=above:\(s_1\)] at (8, 1) (A2) {};
+
+        % draw a line in between the box and the far right of the image
+        \draw[dashed, arrows=<->] (A1) -- node[midway, align=center, above] {\(r\)} (A2);
+    \end{tikzpicture}
+\end{figure}
+~\\[-1.5cm]
+\begin{figure}[H]
+    \centering
+    \begin{tikzpicture}
+        \tikzstyle{circlestyle}=[shape=circle,thick,fill,draw, inner sep=0cm]
+        \node at (0, 0) {};
+        \node at (9, 0) {};
+
+        % draw a big star in the far left of the image
+        \node[circlestyle, minimum size=2pt, label=above:\(q_1\)] at (1, 0) (B1) {};
+
+        % draw the right star
+        \node[circlestyle, minimum size=2pt, label=above:\(s_1\)] at (8, 0) (B2) {};
+
+        % draw a line in between the far left star and the right star
+        \draw[dashed, arrows=<->] (B1) -- node[midway, align=center, above] {\(r\)} (B2);
+    \end{tikzpicture}
+    \label{subfig:grouped}
+    \caption{A cluster of stars that is far enough away from a single star can
+    be abstracted as a single point in space.}
+\end{figure}
+
+\begin{equation} \label{eqn:barnes-hut}
+    \theta = \frac{d}{r}
+\end{equation}
+
+The above equation describes how to cluster the stars. If a body is far away
+(\( >> r\)) from a small cluster (\( << d \) ), \( \theta \) get's very small
+and the cluster in which the body is located can be abstracted to a single
+point.  By defining a \( \theta \) as a threshold, we can define what clusters
+we take into effect when calculating the forces acting on a single star. In
+order to do so, the space in which the objects are defined needs to be
+subdivided into cells. Such a subdivision can be seen in Figure
+\ref{fig:cells}.
+
+\begin{figure}[H]
+\hspace{1.5cm}
+\begin{minipage}{0.45\linewidth}
+\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}
+\caption{Subdivision of a 2D Space containing some bodies. (\url{http://arborjs.org/docs/barnes-hut})}
+\label{fig:cells}
+\end{figure}
+
+When calculating the forces on let's say the object \( F \), not all other
+objects need to be taken into effect, only the ones that apply to the
+Barnes-Hut Principle.  For the object \( F \), this means that the Objects \( C
+\) and \( D \) are not calculated independently, but as one object (The
+midpoint of the center of gravity is defined as a new abstract object).
+
+\begin{figure}[H]
+\centering
+\begin{forest}
+    for tree={circle,draw, s sep+=0.25em}
+    [
+        [A]
+        [
+            [
+                []
+                [B]
+                [C]
+                []
+            ]
+            []
+            []
+            [D]
+        ]
+        [
+            []
+            [E]
+            [F]
+            [G]
+        ]
+        [H]
+    ]
+\end{forest}
+\caption{The cells defined in Figure \ref{fig:cells} displayed in the form of a quad tree. (\url{http://arborjs.org/docs/barnes-hut})}
+\label{fig:tree}
+\end{figure}
+
+In order to simulate the change of position for all objects in the given space,
+a tree can be used.  The tree in Figure \ref{fig:tree} describes the cells from
+Figure \ref{fig:cells} in a form that can be easily programmed. The complete
+process of simulating works in the following way:
+
+\begin{enumerate}
+    \item Define an empty space.
+    \item Insert the objects into the tree subdividing the space if necessary.
+        All the objects need to be places in the leaves of the tree.
+    \item Calculate the center of mass and the total mass for all inner nodes in the tree.
+    \item For calculating the force acting on a star, walk through the tree
+        from the root in direction of the leaves, using the Barnes-Hut
+        Algorithm (\ref{eqn:barnes-hut}) as an end condition. Use \( \theta \)
+        as a threshold for controlling how many forces to take into account (\(
+        \theta = 1 \rightarrow \) all forces, \( \theta = 0.001 \rightarrow \)
+    almost no forces).
+\end{enumerate}
+
+In the end, when simulating a lot of bodies, the runtime is optimized from \(
+O(n^2) \) to \( O(n \cdot \log(n)) \). This means that if you've got \( 2 \cdot
+10^8 \) bodies and can calculate the forces acting on \( 10^6 \) bodies bodies
+per second, the total runtime is reduced from about 1200 Years to 45 minutes
+(this is just the calculation of the forces, inserting the bodies into the tree
+takes a lot of time!).
+
+This principle can also be used on other types of problems such as simulating
+molecules. If you come to do something with it, write me!
+
+\vfill
+
+\texttt{@hanemile} on most platforms.
+
+\newpage
+
+\begin{figure*}
+    \centering
+    \begin{forest}
+        for tree={circle,draw, s sep+=0.25em}
+        [
+            [A]
+            [
+                [
+                    []
+                    [B]
+                    [C]
+                    []
+                ]
+                []
+                []
+                [D]
+            ]
+            [
+                []
+                [E]
+                [F]
+                [G]
+            ]
+            [H]
+        ]
+    \end{forest}
+    \caption{The cells defined in Figure \ref{fig:cells} displayed in the form of a quad tree. (\url{http://arborjs.org/docs/barnes-hut})}
+    \label{fig:tree}
+\end{figure*}
+
+\end{document}