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 ++++++++++++++ barneshut.tex | 412 +++++++++++++++++++++ .../barneshut.pdf | Bin 0 -> 101042 bytes .../main.pdf | Bin 68278 -> 0 bytes current-build | 2 +- last-successful | 2 +- main.tex | 218 ----------- 7 files changed, 682 insertions(+), 220 deletions(-) create mode 100644 .hidden/main.tex create mode 100644 barneshut.tex create mode 100644 build-f559a2f9bea2a19c5ac7b586fba6405283df896bebf7891937013019df99d759/barneshut.pdf delete mode 100644 build-f747a3fa645a454646cf1bb8557e49524dc7d9326a3d2e7cd18a7caf3f05c672/main.pdf delete mode 100644 main.tex 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} 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} diff --git a/build-f559a2f9bea2a19c5ac7b586fba6405283df896bebf7891937013019df99d759/barneshut.pdf b/build-f559a2f9bea2a19c5ac7b586fba6405283df896bebf7891937013019df99d759/barneshut.pdf new file mode 100644 index 0000000..d995929 Binary files /dev/null and b/build-f559a2f9bea2a19c5ac7b586fba6405283df896bebf7891937013019df99d759/barneshut.pdf differ diff --git a/build-f747a3fa645a454646cf1bb8557e49524dc7d9326a3d2e7cd18a7caf3f05c672/main.pdf b/build-f747a3fa645a454646cf1bb8557e49524dc7d9326a3d2e7cd18a7caf3f05c672/main.pdf deleted file mode 100644 index 3d55efd..0000000 Binary files a/build-f747a3fa645a454646cf1bb8557e49524dc7d9326a3d2e7cd18a7caf3f05c672/main.pdf and /dev/null differ diff --git a/current-build b/current-build index 2fd5fed..17e1c8a 120000 --- a/current-build +++ b/current-build @@ -1 +1 @@ -build-f747a3fa645a454646cf1bb8557e49524dc7d9326a3d2e7cd18a7caf3f05c672 \ No newline at end of file +build-f559a2f9bea2a19c5ac7b586fba6405283df896bebf7891937013019df99d759 \ No newline at end of file diff --git a/last-successful b/last-successful index 2fd5fed..17e1c8a 120000 --- a/last-successful +++ b/last-successful @@ -1 +1 @@ -build-f747a3fa645a454646cf1bb8557e49524dc7d9326a3d2e7cd18a7caf3f05c672 \ No newline at end of file +build-f559a2f9bea2a19c5ac7b586fba6405283df896bebf7891937013019df99d759 \ No newline at end of file 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} -- cgit 1.4.1