diff options
| -rw-r--r-- | build-f747a3fa645a454646cf1bb8557e49524dc7d9326a3d2e7cd18a7caf3f05c672/main.pdf | bin | 0 -> 68278 bytes | |||
| l--------- | current-build | 1 | ||||
| l--------- | last-successful | 1 | ||||
| -rw-r--r-- | main.tex | 218 |
4 files changed, 220 insertions, 0 deletions
diff --git a/build-f747a3fa645a454646cf1bb8557e49524dc7d9326a3d2e7cd18a7caf3f05c672/main.pdf b/build-f747a3fa645a454646cf1bb8557e49524dc7d9326a3d2e7cd18a7caf3f05c672/main.pdf new file mode 100644 index 0000000..3d55efd --- /dev/null +++ b/build-f747a3fa645a454646cf1bb8557e49524dc7d9326a3d2e7cd18a7caf3f05c672/main.pdf Binary files differdiff --git a/current-build b/current-build new file mode 120000 index 0000000..2fd5fed --- /dev/null +++ b/current-build @@ -0,0 +1 @@ +build-f747a3fa645a454646cf1bb8557e49524dc7d9326a3d2e7cd18a7caf3f05c672 \ No newline at end of file diff --git a/last-successful b/last-successful new file mode 120000 index 0000000..2fd5fed --- /dev/null +++ b/last-successful @@ -0,0 +1 @@ +build-f747a3fa645a454646cf1bb8557e49524dc7d9326a3d2e7cd18a7caf3f05c672 \ No newline at end of file diff --git a/main.tex b/main.tex new file mode 100644 index 0000000..354162c --- /dev/null +++ b/main.tex @@ -0,0 +1,218 @@ +\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} + +% custom imports +\usepackage{float} +\usepackage{tikz} +\usepackage{forest} + +\pagenumbering{gobble} + +\title{Clustering bodies using the Barnes-Hut algorithm accelerating simulations} +\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 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 about \( 4 \cdot 10^{16} \). + +This can be reduced by utilizing the Barnes-Hut algorithm clustering the bodies. + +\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 summed up 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. +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.} +\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 independantly, but as one object (The +midpoint of center of gravity is defined as a new 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} dispayed in the form of a quadtree.} +\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 subdividing the space if necessary. + \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 codition. +\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 \( 1 \cdot 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 alot of time!). + + +\end{document} |
