diff options
Diffstat (limited to 'main.tex')
| -rw-r--r-- | main.tex | 218 |
1 files changed, 0 insertions, 218 deletions
diff --git a/main.tex b/main.tex deleted file mode 100644 index 354162c..0000000 --- a/main.tex +++ /dev/null @@ -1,218 +0,0 @@ -\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} |
