1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
|
\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}
|
