diff options
Diffstat (limited to 'barneshut.tex')
| -rw-r--r-- | barneshut.tex | 412 |
1 files changed, 412 insertions, 0 deletions
diff --git a/barneshut.tex b/barneshut.tex new file mode 100644 index 0000000..cc2734d --- /dev/null +++ b/barneshut.tex @@ -0,0 +1,412 @@ +\documentclass[twocolumn, 10pt]{article} + +\usepackage{geometry} +\geometry{ + a4paper, + total={6.85in, 9.92in}, + top=16mm, + bottom=29mm, + left=18mm, + right=18mm, +} + +% show page frame +\usepackage{showframe} + +\usepackage[utf8]{inputenc} +\usepackage{hyperref} +\usepackage{listings} +\usepackage{float} +\usepackage{tikz} +\usepackage{forest} +\usepackage{scrextend} +\usepackage{caption} +\usepackage{subfig} + +\pagenumbering{gobble} + +\title{Accelerating simulations by clustering bodies using the Barnes-Hut algorithm\vspace{-5mm}} +\author{Paged 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[ +\vspace{-3mm}\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.35\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 +\subfloat[some caption 1]{ + \begin{tikzpicture}[level 1/.style={level distance=1.5cm}, scale=0.5, every node/.style={scale=0.66}] + % 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} +} +\subfloat[some caption 2]{ +\begin{forest} + for tree={circle,draw, s sep=0.2em, font=\scriptsize} + [ + [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. + +\begin{figure*} + %for tree={circle,draw, s sep+=0.25em} + + % First + \begin{minipage}[t]{.24\textwidth} + \centering + % Cells + \begin{tikzpicture} + \draw (0, 0) rectangle (2, 2); + \end{tikzpicture} + ~\\ + % Tree + \begin{forest} + for tree={circle,draw, s sep+=0.25em} + [] + \end{forest} + % Caption + \captionof{figure}{Caption} + \end{minipage} + % Second + \begin{minipage}[t]{.24\textwidth} + \centering + % Cells + \begin{tikzpicture} + % Layer 0 + \draw (0, 0) rectangle (2, 2); + + % Layer 1 + \draw (0, 0) rectangle (1, 1); + \draw (1, 0) rectangle (2, 1); + \draw (0, 1) rectangle (1, 2); + \draw (1, 1) rectangle (2, 2); + + % Nodes + \node at (0.25, 0.25) {A}; + \end{tikzpicture} + ~\\ + % Tree + \begin{forest} + for tree={circle,draw, s sep=3mm} + [ + [][][A][] + ] + \end{forest} + % Caption + \captionof{figure}{Caption} + \end{minipage} + % Third + \begin{minipage}[t]{.24\textwidth} + \centering + % Cells + \begin{tikzpicture} + % Layer 0 + \draw (0, 0) rectangle (2, 2); + + % Layer 1 + \draw (0, 0) rectangle (1, 1); + \draw (1, 0) rectangle (2, 1); + \draw (0, 1) rectangle (1, 2); + \draw (1, 1) rectangle (2, 2); + + % Layer 2.1 + \draw (0, 0) rectangle (0.5, 0.5); + \draw (0.5, 0) rectangle (1, 0.5); + \draw (0, 0.5) rectangle (0.5, 1); + \draw (0.5, 0.5) rectangle (1, 1); + + % Nodes + \node at (0.25, 0.25) {A}; + \node at (0.75, 0.75) {B}; + \end{tikzpicture} + ~\\ + % Tree + %\begin{forest} + % for tree={circle,draw, s sep=3mm} + % [ + % [] + % [] + % [ + % [][][A][] + % ] + % [] + % ] + %\end{forest} + % Tree (2) + \begin{forest} + for tree={circle,draw, s sep=3mm} + [ + [] + [] + [ + [][B][A][] + ] + [] + ] + \end{forest} + % Caption + \captionof{figure}{Caption} + \end{minipage} + % Fourth + \begin{minipage}[t]{.24\textwidth} + \centering + % Cells + \begin{tikzpicture} + % Layer 0 + \draw (0, 0) rectangle (2, 2); + + % Layer 1 + \draw (0, 0) rectangle (1, 1); + \draw (1, 0) rectangle (2, 1); + \draw (0, 1) rectangle (1, 2); + \draw (1, 1) rectangle (2, 2); + + % Layer 2.1 + \draw (0, 0) rectangle (0.5, 0.5); + \draw (0.5, 0) rectangle (1, 0.5); + \draw (0, 0.5) rectangle (0.5, 1); + \draw (0.5, 0.5) rectangle (1, 1); + + % Nodes + \node at (0.25, 0.25) {A}; + \node at (0.75, 0.75) {B}; + \node at (1.75, 1.75) {C}; + \end{tikzpicture} + ~\\ + % Tree + \begin{forest} + for tree={circle,draw, s sep=3mm} + [ + [] + [C] + [ + [][B][A][] + ] + [] + ] + \end{forest} + % Caption + \captionof{figure}{Caption} + \end{minipage} +\end{figure*} + +\end{document} |
