[MUSIC]

Hi and welcome again to our class, Simulation and

Modeling of Natural Processes.

The next module is about the n-body problem

in which we talk about how to evaluate gravitational forces.

Remember the example I showed you of two colliding galaxies.

Notice how these two galaxies rotate around a common center of mass.

We do not model this rotation around the common center of mass explicitly.

The only thing we actually model here

is the individual interaction between pairs of stars.

The rotation around the common center of mass is

an emergent behavior from the pairwise interactions of all bodies in this system.

This means that this is a system with long range forces.

All stars in the system are effected by the position of all other stars.

Remember that in the previous module we talked about the Lennard-Jones potential,

and we saw that we could reduce and

simplify the problem, by introducing a cut-off length,

which means we were considering limiting interaction between particles and

some nearby particles which were contained within a cut-off length.

We cannot do this in the case of a n-body problem

because all other star's are important, there's no one we can eliminate.

However there exists other techniques to make the calculations easier and

we're going to talk about them now.

One very frequently used approach are so called tree methods.

The idea in this method is that if a group of bodies is

sufficiently far away that we model this group as one single body,

which is positioned at the center of mass of the group, and

which has the mass of all bodies inside this group.

Imagine for example that you were about to simulate the interaction between

billions of galaxies.

Then for sure you would not model each single star inside these galaxies.

You would just model the galaxies themselves as single particles,

as single bodies with a given center of mass,

a given mass which is the aggregated mass of all stars in the system.

In tree methods, the idea is that we generalize this approach.

By regrouping portions of space and

represent these groups by their center of mass to speed up the calculations.

Consider for example the case of ten interacting bodies.

Of course,

if you have just ten bodies, taking into account all pairwise interactions,

which will be of the order of ten squared, which is 100, would not be a problem.

It is only a problem when you have a large amount of bodies.

But we use the case of ten bodies to illustrate the concept and

then show how these generalize to bigger problems.

In this case we would like to compute

the resulting gravitational force which acts on body 1.

Gravitational forces are non-local, so we never lose force approach.

We need to take into account interaction between body one,

the red body, and all its nine partners.

We need to compute nine forces and sum them up.

But the idea is you can speed up the calculation.

It would take a group of bodies, like in this case bodies seven,

eight and nine and treat them as a single body.

Placed at the center of mass, and treat the interaction between

these three bodies and body one as a single interaction.

This is a reasonable approximation if this group is far away.

If it was very close to body one,

we would need to take into account the interaction of every single body.

Because every single body would be relatively positioned

at very different distances and angles with respect to body one.

But if they are far away,

the relative difference of the distance of the different bodies,

seven, eight, and nine, throughout the angle of the vector which points

from body one to these other bodies would differ only a very little.

It is reasonable to approximate them by their position in the center of mass.

But the question is, how do we define these groups?

One approach would be to say,

let's do the same thing as we did with the Lennard-Jones potential and

superpose a grid, a regular space grid, to the space of the object.

We would then use this regular subdivision and treat as groups or

bodies, which are placed within one cell of this regular grid.

In this case, this happens to work for the group of bodies, seven, eight, and

nine which we were talking about before.

They are all in the same cell and we treat them as a single group.

But although sometimes this strategy works, sometimes it fails,

because bodies two and three are also placed within one cell, but

they are very close to body number one.

In this case, the approximation is not a good one.

We would need to treat the interaction between body one and

body two and three individually, as pairwise interactions.

Approximating them by the center of mass is not a good approximation.

As a matter of fact, in this case we need to have groups of different sizes.

Small groups for the ones which are nearby, and

large groups for the ones which are distant, for the distant bodies.

One solution are tree algorithms in which we recursively subdivide space into first,

large groups and then smaller and smaller groups.

Each body in the system is enclosed by both small groups and large groups,

which means that when we try to consider the interaction with these bodies,

we can select a group of a size which is appropriate for

the problem we are considering, which means the size of the group is

appropriate with the distance between the body on which the force acts and

the group for which we are considering the interaction.

There exist different tree based algorithms for treating this problem.

And then I'm going to introduce here a very classic one

which is called the Barnes-Hut algorithm.

In the Barnes-Hut algorithm space is subdivided into

quadrants in a 2D case, and in octants in 3D space.

Which means that in 2D, we recursively take a square and

subdivide it into four octants and take these octants again and

subdivide them into four smaller octants and so on.

In 3D volume, a block is subdivided into octants,

which are subdivided again and again.

On the right-hand side of this image You see a graph which

represents the recursive structure of the quad-tree on the left.

I'm going now to show you exactly what this graph means and

show you how we create these graphs from the position of the bodies in the system

at a given time set.

But, first, let's introduce some naming.

If we take the full space, the full square, and

subdivide it into four quadrants,

we will have a quadrant which is located at the right left of the system.

We call this the southeast quadrant.

And on top of it the northeast quadrant at the top right.

At the lower left you have the southwest quadrant, and

on top of it, the northwest quadrant.

On the right-hand side of this scheme, we're going to construct

a graph which represents the recursive structure of these coordinates.

We start the graph by a single point which represents full space, a blue dot.

Now that we subdivide space into four quadrants, this dot

gets up to four children, which representing the quadrants.

We will take these children always in the same order.

We start with the southeast quadrant, which is the left-most child

of the root node of the tree, followed by the northeast quadrant,

which will be the second child of the root of the tree.

Then the southwest quadrant and, finally, the northwest quadrant.

We have now a tree, which has a root node which is blue, and

four children nodes representing the four quadrants of space.

Let's now take our stellar bodies and insert them into this data structure.

Let's start with the first one which is body number one.

You can see that body number one is placed in the southeast quadrant.

This means that we take it and add it to the tree structure

on the left-most branch which represents the southeast quadrant.

The stellar body is now on the so-called exterior node of the tree

because it is a final node in the graph structure,

it does not have, for now, any children nodes.

But this might change in the future, as we will see.

We will now introduce the second body and put it into the tree.

The second body is placed in the northeast quadrant, which means that we put it

into the second branch, or on the leaf of the second branch in the graph structure.

It is, again, an exterior node, and that node of the tree.

The third body happens to also find itself in the second quadrant, which means that

it will be in conflict with the position of the second body inside the tree.

By definition, this tree is constructed in such a way

that all nodes of the tree can contain at most one single body.

We, therefore, need to resolve this conflict, which we do by taking

this North-East quadrant and subdivide it into four smaller quadrants.

At this second level of recursion we will draw the quadrants in green color, whereas

at the first recursion level we used a red color to represent the quadrants.

At the second level of recursion, the northeast quadrant, the red,

northeast quadrant, is subdivided into four green quadrants,

which again will travel in the same order.

The green quadrants are traveled first by the southeast, then the northeast,

and so on, quadrants.

Let's start with the southeast where the bodies which have collided,

which have been in conflict, bodies two and three, happen again to find themselves

in the same quadrant at the second recursion level.

So even at the second recursion level, we have a conflict with the position of these

two bodies because they try to be positioned in the same node as the tree.

We, therefore, need to take this tree and subdivide it once more.

We take the green southeast quadrant and subdivide it once more

into four black quadrants, which is at the third recursion level.

At the third recursion level, well, the two bodies,

two and three, are not colliding any more because body number 2 is

placed in the southeast quadrant, which is the first branch of this tree,

and the third body is placed in the northwest quadrant.

In this case, we are done with the recursion, and

have been able to place bodies 2 and 3 on exterior nodes of the graph, on n nodes,

in which they are alone as they should be by definition inside this tree.

As we insert these bodies into the tree, every node, no matter at

which level of recursion it is and no matter whether it is an interior or

an exterior node, has a given mass and a given center of mass.

Remember that every node represents

one given quadrant in the system of a given size.

If the node is at the first recursion level,

it will represent one of the big red quadrants.

If it is at the second recursion level,

it will represent one of the smaller green quadrants.

And at the third recursion level, one of the very small black quadrants.

Every one of these quadrants, potentially,

contains some bodies, which can be several of them.

At the last recursion level, in extreme loads,

they by definition only have one body.

But at a higher recursion level, for

example the red quadrant, there might be several bodies inside.

Therefore, we need, as whenever we introduce a new body,

to reupdate the center of mass assigned to every one of these nodes.

When we have two bodies, for example, inside a quadrant, well,

the total mass of the quadrant in which these two bodies are placed

is just the sum of the two bodies, of course.

And the center-of-mass, it's just

the weighted sum of the position of these two bodies, which means

the position of the center-of-mass is the position of the first body times its mass

plus the position of the second body times its mass again, divided by the total mass.

By now, through this example, I think that you have more or

less understood the algorithm which we apply to insert bodies recursively

into the tree and to update the values of total mass and

the center-of-mass of every node inside this tree.

But let's formalize this algorithm.

In this algorithm, we take a body, b, and start inserting

it into a tree recursively by starting with the root node, n.

Inside this recursion, if a node is empty, which means it does not already

contain a body, then when we are done we just take the body, b, and put it there.

And we have a new n node with this body, b.

But if on the other hand the node is an internal node,

which means it contains children, then while this node will

represent a portion of space In which we have right now introduced a new body,

which means that this node needs to update its total mass and

its center of mass in order to take into account the mass and

position of the new body b.

Then, we recursively insert a body b into the appropriate quadrant, which is

one of the children of this node, by repeating over again the same algorithm.

Finally, if the node n in which we try to place the body is already

an exterior node then this means that it already contains previous body which

was previously inserted which collides with the body we are trying to insert.

In this case, we need to further cell divide the base node into four

quadrants and place the two bodies which were in conflict into their appropriate

quadrant and reapply this procedure recursively if they collide again.

And that's what we do with this.

Whenever we treat a new node, we update the center-of-mass of this

new node to take into account the mass of the two conflicting bodies.

We also of course, update the center of mass, to take into account their position.

Now that we have this cost of the general terms of the algorithm,

let's finish inserting all of the ten particles, or

all of the ten stellar bodies which we have in this system.

We're down with inserting body two and three, which were colliding and

which we have to take to the third recursion level to

find n nodes in which they are separate from each other.

Body number four is placed into the northeast quadrant

at the first recursion level, which means the northeast right quadrant.

The northeast right quadrant is all ready and

then t nodes there are all ready bodies there.

So we go at the next level, at the green level,

the second recursion level and see that this recursion level,

the new body goes into the northeast quadrant which is empty.

We therefore create a new n node and

place body number four into this quadrant.

Body number five, and

we are going to take shortcuts now because I think that you understood the concept.

Body number five is in the same red quadrat and

the same green quadrant as body number four.

We therefore need to take this quadrant and

subdivide it into two black quadrants at the third recursion level and

place the four colliding bodies four and five into their own third level quadrant.

After which, we insert all the remaining bodies, six, seven, eight, nine, and ten.

We see that the first recursion level, the red level, one quadrant remains empty.

It is the southwest quadrant.

For this quadrant, we don't allocate anything.

It does not exist in the tree we have just created.

On the other hand, the northwest quadrant has a total of four particles.

One of which, particle 10, is in its own green quadrant,

whereas particles seven, eight and nine collided or

were in conflict in the northeast green quadrant and

were subdivided into block third level quadrants.

On the right-hand side, you now see the full tree.

All bodies are end nodes in this tree, and they are represented by an orange node.

The blue nodes are interior nodes at which we have placed no body, but

which represents a portion of space which contain the bodies which

are the children of these nodes.

They have their own center of mass and their own total mass which we

have computed and updated and insert it in your bodies.

Now that we have created this tree structure,

we are ready to apply it and use it to efficiently compute

the forces which act from all other bodies on to one given body.

But we will take

this to the next module.

This ends our current module on the creation of an tree, or

a quadtree in according to the Barnes-Hut algorithm.

In the next module, we'll describe how we use this quadtree.

Thank you. [MUSIC]

The n-body problem: Evaluation of gravitational forces

Simulation and modeling of natural processes

Meet the Instructors