From 449ba33b194f79d928663486bc24fee4d0073d4f Mon Sep 17 00:00:00 2001 From: Emile Date: Mon, 22 Jul 2019 15:23:42 +0200 Subject: save --- .hidden/main.tex | 268 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 268 insertions(+) create mode 100644 .hidden/main.tex (limited to '.hidden') 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} -- cgit 1.4.1