0:18

In our previous model we have introduced an algorithm called

the Barnes-Hut algorithm.

This algorithm can be used to accelerate the calculations of an n-body system,

a system in which we are calculating the interaction between and

a big amount of cellular bodies under the influence of gravity.

0:42

This algorithm is a so-called tree algorithm,

and it subdivides space into quadtrees in 2D and

octrees in 3D to represent groups,

portions of space in groups which can potentially be used as a single body,

to simplify the interaction with a body, between a body, and this portion of space.

1:08

We have seen in the previous module how to create such a quadtree intuitively,

or octree tree in 3D.

And we will now see how to use the previously built tree

to calculate the force, the net force of all other cellular bodies

onto one body, in our case body number one.

To do so we have to recurse into our tree and

consider all of its leaves recursively.

1:37

At the first level, we consider the first quadrants,

direct quadrants which divide the four space into four portions.

If they are far enough from body number one, we can use their mass and

their center of mass to simplify

interactions between body one and all bodies which are inside this quadrant.

And represented by a single body located at the center of mass.

2:16

Let's see how this works.

We are interested in the net force acting on body one, which in this image, is red.

To do this we recurse into our tree and start at the first recursion level.

The level of the red quadrant of which we have totally for.

2:35

The first quadrant is the southeast quadrant.

It contains just one body, body number one.

But body number one does not exert any force onto itself.

So we will reject this one, and

instead go on with the second quadrant, the northeast quadrant.

This quadrant contains totally five bodies.

We have previously computed the center of mass of this quadrant and we can now

compute the distance between body one and the center of mass of this quadrant.

3:17

If these five bodies are far enough, then we can accept this abstraction.

If they are too close, we cannot represent them by the center of mass.

What does too far or too close mean?

It depends also on the size of the group which we are considering.

Because very far away bodies can't be represented by big groups, but

close bodies can only be represented by quite small groups.

So we need to consider also the side lengths of the quarter

representing the group of these five stellar bodies.

3:52

What really matters is not the actual value of d or the actual value of c of s,

but the relationship between these two, which means the ratio between s and d.

We call this the theta-criterion.

We will accept a given quadrant and

represent its bodies by their center of mass.

If the ratio between s and d, s over d,

4:24

can be chosen according to the requirements of your simulation.

If theta is zero, then, or

if theta is close to zero, what that means is that we will not,

accept any representation of groups of bodies by the center of mass.

And consider all pair wise interactions between all cellular bodies.

Your algorithm will be n square.

4:49

If on the the other hand theta is quite big,

then you will expect quite a lot of approximation.

It would not be very efficient numerically but

we'll take into account potentially large numerical errors.

Coming from the representation of many stars, by a center of mass of the group.

5:11

Quite a frequent value for theta is theta equal one half.

And this is the value to use as an example in this presentation.

But of course, quite all the value are used as well in numerical simulation.

Here theta T times one half,

then the theta-criterion amount to saying that s over d is less than one half.

Or to put it into other words, d is larger than 2s.

Which means the distance between our body and the center of mass

of the quadrant is larger than twice the side length of this quadrant.

Is the theta-criterion verified in our case.

We see now visually the length of d and length of s.

And it is, we can immediately tell that the d is not larger than twice s.

The theta-criterion is obviously not verified here.

The d and s have almost the same length.

We therefore need to recurs in to the red quadrants and consider

four green sub-tress, it's sub quadrants.

From the right, at the first recursion level, we can see that the right quadrant,

and we are now recursing into the second level where we are continuing

to form green quadrants, which are contained inside the retinal quadrant.

We start with the first green quadrant, which is the southeast quadrant.

I need to decide again if the two bodies contained in this quadrant can be

approximated by the center of Mars, so we start the whole procedure over again.

We calculate the distance d between body one, and the center of Mars of this

quadrant and compare it to the side length of this quadrant.

7:01

Again, just visually by look at this example, you can immediately tell

that the distance, d is not larger than twice the side length s.

So this column again must be rejected.

7:30

We curse now at the third level and consider the black quadrants which

are nodes of the trees, which means they just contain single bodies.

At this level we just accept bodies by default of course, because we are back

at the most simple case of pure wise interactions between body one and

the bodies two and three.

8:11

We are right now in the northeast red quadrant and

we're traversing the green quadrant contained inside this red quadrant.

We are done with the first green quadrant which was the southeast quadrant,

and we are going on with the northeast quadrant.

Which contains again two bodies, body four and body five.

We do the same procedure all over again computing the distance.

Between body one and the center of mass of this quadrant.

And compare this distance d with twice the side length of this quadrant, 2s.

8:51

If you put 2s and d next to each other,

you'll see that this time the feta criteria is verified.

D is larger than 2s in this case.

We can't use the abstraction of representing bodies four and

five by the center of mass.

9:08

The center of mass has been previously calculated and

is stored inside this node of the quadrant.

We can therefore, right away calculate the net force of these

two bodies onto body one and add it to the total force acting on body one.

9:59

a node which has no children, and if this node is not actually equal to our body b,

then you just consider a pair wise interaction between b and

the body defined at this node.

And add this amount to the net force acting on body b.

10:20

If it is an interior node, we need to decide wether we can

use all bodies which are contained in the quadrant

of this node and abstract them as a single body at the center of mass.

We need to apply the theta-criterium.

By calculating the ratio s/d, between the between the side length of the quadrant s,

and the distance d between the body b and the center of more mass of this quadrant.

If s/d is less than theta, we treat this internal node as a single body,

and calculate the force it exerts on body b.

Add it to the total net force acting on body b.

11:02

If on the other hand, the theta-criterion is not verified,

we have to go on with the recursive procedure.

And recurves into the children off node, of the quantitative node.

11:17

Now that we have talked about

the algorithm in general terms.

We can go through the full procedure of calculating the net

force of our nine partner bodies onto body number one.

We have so far treated the interaction of body round with body two,

three, four and five, and continue with body six.

Which is in the southwest quadrant, green quadrant of the northeast direct quadrant.

It is alone over there, so

we'll just treat it as a pairwise interaction by default.

Going on with the last red quadrant, which is the northwest quadrant.

We start by rejecting the hypothesis that

these red quadrant can be considered as a single body

because it is quite obvious by now that they will be too close to body number one.

And instead recurs into the green quadrant.

The first one, the north east one, has three bodies, which

are represented by the center of mass and which do verify the center criterion.

We can't treat them as a single body.

And finally, body number ten is again alone inside this green quadrant.

We treat it as a single pair wise interaction.

With this, we have finished the trouble,

solved the tree and have computed the total net force of all bodies.

Acting on body one at one time step of the recursive,

of the iterative time stepping scheme of our numerical algorithm.

12:57

In this particular case, traversing this complicated tree has for

sure not been numerically more efficient

than just treating all n squared interactions between these bodies.

But there were just ten bodies.

13:12

If there have been, let's say, one billion bodies,

traversing this tree would have been much cheaper than considering n squared,

which is a billion squared pair wise interactions.

13:37

But it many cases, it can be shown theoretically that the total

complexity of this algorithm is equal to n n times the logarithm of n,

which is very close to a linear complexity n.

We again have an algorithm which is numerically very efficient like

the algorithm based on the value and a grid-based data structure

which we applied in molecular dynamics for the Lennard-Jones potential.

14:09

If for example, you were treating 5,000 bodies instead of 10,

you would just apply the exact same procedure.

You see here example,

the 5,000 bodies which we consider in the case of 2 colliding galaxies.

14:56

Using a theta value of 0.7, you see that

close to the body you will need to use quadrants which are quite small, but

far from this body, you will be able to use very large bodies.

In particular, the small galaxy which gravitates

around the large galaxy can be represented by approximately four quadrants.

The interaction of this far away galaxy with our

red point can be calculated extremely efficiently by

using taking to account only a little bit more than four terms.

15:37

This ends our module on the Barnes-Hut algorithm on using a quadtree.

It also ends today this week, and

it ends our class on particle methods and

in general, on poly like approximations of

systems with many particles or many bodies.

Thank you for your attendance.

[MUSIC]