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
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
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}
|