path: root/.hidden/main.tex

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