Hi, and welcome again to our class, Simulation and

Modeling of Natural Processes.

In the present module, we go back to one of the potentials which we have

introduced, the Lennard-Jones potential.

And we'll talk about about how to solve interaction

with this potential in an efficient way by introducing a cut off distance.

You remember from the previous module that I showed you

a way to integrate Newton's equations of motion,

in the case of a system of many bodies or many particles.

We introduced a Verlet scheme in which we took the system from non-discrete

time to the next discrete time.

Now we saw that this discrete scheme was very efficient computationally,

but there was one expensive operation hidden in this scheme.

This expensive operation is the calculation of the forces

acting on the bodies around the particles which we use

to evaluate the acceleration of the particles then integrated.

Let's go back to the case of N particles interacting with each other

through a potential, in this case the Lennard-Jones potential.

As a matter of fact, it could be any other potential.

In principle if you want to calculate the force acting on a given body,

in this case on body one, you need to take into account the force which comes

from all the other bodies which will perpetually act on the given body.

I show you now an example with a total of ten bodies, which means if you want

to know the force acting on body one you need to calculate nine interaction terms.

Of course, in a bigger system if you have a galaxy with 400 billion bodies,

you will have to calculate 400 billion forces acting

on the given body if you do it in a brute force approach.

We say that, in this case, the algorithm has a complexity ends

clear which means the algorithm are just computing all the forces

on all bodies acting on the system at a given discrete time, and

takes a number of operations which is proportionate to n squared.

Because, first of all, you have to calculate the force for

every one of these n bodies.

And then for every one of these n bodies,

you have to calculate the interaction with all the n minus one other bodies.

Of course in the case of gravity, and

as a matter of fact in the case of all the other forces which we introduced here,

because of Newton's Third Law, the forces are symmetric.

The force of body A acting on Body B Is equal in

norm to the force of body B acting on body A.

So we really only have to evaluate half of these forces.

So, the total of amount of operations is n(n-1)/2 but

still the leading term of this expression is n square so

this is a n square algorithm which can be extremely expensive,

except if you apply an intelligence scheme to shorten the computation.

Let's see what a complexity of n square means.

On this graph, I have plotted on the x-axis a value

of n which ranges from zero to ten to the power 12.

Along the y-axis I have simply plotted the square of this value.

This graph is plotted on a log-log scale,

which means that both the x and the y axis are logarithmic.

On the log-log scale, the n square curve is a linear curve.

It shows us how many calculations we need to do to perform

to compute all forces at one iteration of our time stepping scheme.

And I have showed you to give you an order of magnitude which type of computers

we have available nowadays can compute which amount of interactions.

Of course,

the number of interactions a computer can evaluate depends on many factors.

It depends of the type of potential which is being used.

It also depends on the kind of algorithm you use to implement interaction

between the bodies on the data structure which is being implemented.

And you will see shortly different type of data structures which we will use

in different types of contexts.

So the computational power, which I am estimating here,

is really just a rough estimation, and

you should take it as an order of magnitude and not an exact value.

You can see here that if you are calculating these interactions with

a desktop computer, you can just compute the interaction between

a few thousand bodies or a few thousand particles, and that's all.

The worlds fastest super computer,

if it uses a brute force n square algorithm to evaluate all interaction,

can just handle a system of around 1million particles and not more.

This is not allowed.

The number of stars you need to simulate fi you want to simulate our

galaxy is approximately 400 billion.

In this case, if you take the square of 400 billion,

you will see that you have so many interactions to take into account that

you will need 100 billion of the world's fastest supercomputer just

to evaluate these interactions at one time step in a reasonable time.

This is completely unrealistic.

It's unrealistic nowadays, and also in the near future,

you will not be able to reach this computational power.

This shows you that it is not possible for

interesting problems like the stars in the galaxy, or

even where the molecules which you have in a gas,

to use a computer to evaluate all the n square interactions.

We need to find shortcuts,

ways to simplify the problem to make the computations faster.