path: root/barneshut.tex

\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}