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]

Â