diff options
| -rw-r--r-- | .hidden/main.tex (renamed from main.tex) | 104 | ||||
| -rw-r--r-- | barneshut.tex | 412 | ||||
| -rw-r--r-- | build-f559a2f9bea2a19c5ac7b586fba6405283df896bebf7891937013019df99d759/barneshut.pdf | bin | 0 -> 101042 bytes | |||
| -rw-r--r-- | build-f747a3fa645a454646cf1bb8557e49524dc7d9326a3d2e7cd18a7caf3f05c672/main.pdf | bin | 68278 -> 0 bytes | |||
| l--------- | current-build | 2 | ||||
| l--------- | last-successful | 2 |
6 files changed, 491 insertions, 29 deletions
diff --git a/main.tex b/.hidden/main.tex index 354162c..90496dc 100644 --- a/main.tex +++ b/.hidden/main.tex @@ -10,15 +10,23 @@ \usepackage[utf8]{inputenc} \usepackage{hyperref} \usepackage{listings} - -% custom imports \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{Clustering bodies using the Barnes-Hut algorithm accelerating simulations} +\title{Accelerating simulations by clustering bodies using the Barnes-Hut algorithm} \author{Page Out!} \makeatletter @@ -38,13 +46,13 @@ ] 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. +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 @@ -101,7 +109,7 @@ This can be reduced by utilizing the Barnes-Hut algorithm clustering the bodies. \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.} + be abstracted as a single point in space.} \end{figure} \begin{equation} \label{eqn:barnes-hut} @@ -109,12 +117,12 @@ This can be reduced by utilizing the Barnes-Hut algorithm clustering the bodies. \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 +(\( >> 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] @@ -153,15 +161,15 @@ subdivided into cells. Such a subdivision can be seen in Figure \node at (3.5, 0.75) {$H$}; \end{tikzpicture} \end{minipage} -\caption{Subdivision of a 2D Space containing some bodies.} +\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 independantly, but as one object (The -midpoint of center of gravity is defined as a new object). +\) 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 @@ -189,7 +197,7 @@ midpoint of center of gravity is defined as a new object). [H] ] \end{forest} -\caption{The cells defined in Figure \ref{fig:cells} dispayed in the form of a quadtree.} +\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} @@ -200,19 +208,61 @@ 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 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 codition. + 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 \( 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!). +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 --- /dev/null +++ b/build-f559a2f9bea2a19c5ac7b586fba6405283df896bebf7891937013019df99d759/barneshut.pdf Binary files differdiff --git a/build-f747a3fa645a454646cf1bb8557e49524dc7d9326a3d2e7cd18a7caf3f05c672/main.pdf b/build-f747a3fa645a454646cf1bb8557e49524dc7d9326a3d2e7cd18a7caf3f05c672/main.pdf deleted file mode 100644 index 3d55efd..0000000 --- a/build-f747a3fa645a454646cf1bb8557e49524dc7d9326a3d2e7cd18a7caf3f05c672/main.pdf +++ /dev/null Binary files differdiff --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 |
