This course gives you an introduction to modeling methods and simulation tools for a wide range of natural phenomena. The different methodologies that will be presented here can be applied to very wide range of topics such as fluid motion, stellar dynamics, population evolution, ... This course does not intend to go deeply into any numerical method or process and does not provide any recipe for the resolution of a particular problem. It is rather a basic guideline towards different methodologies that can be applied to solve any kind of problem and help you pick the one best suited for you. The assignments of this course will be made as practical as possible in order to allow you to actually create from scratch short programs that will solve simple problems. Although programming will be used extensively in this course we do not require any advanced programming experience in order to complete it.
The n-body problem: Evaluation of gravitational forces
Loading...
From the course by University of Geneva
Simulation and modeling of natural processes
55 ratings
From the lesson
Particles and point-like objects
A short review of classical mechanics, and of numerical methods used to integrate the equations of motions for many interacting particles is presented. The student will learn that the computational expense of resolving all interaction between particles poses a major obstacle to simulating such a system. Specific algorithms are presented to allow to cut down on computational expense, both for short-range and large-range forces. The module focuses in detail on the Barnes-Hut algorithm, a tree algorithm which is popular a popular approach to solve the N-Body problem.
Meet the Instructors
Bastien ChopardFull Professor
Computer Science
Jean-Luc FalconeResearch Associate
Computer Science
Jonas LattSenior Lecturer
Computer Science
Orestis MalaspinasResearch Associate
Computer Science Department
[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]
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
