0:11

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.

Â 7:02

Again, to summarize the problem we are treating,

Â a brute force approach for treating a system of n objects is ten square.

Â We cannot solve that nowadays with the available power.

Â Strategies are required to reduce the valid calculations.

Â But let's go back to the Lennard-Jones potential.

Â Because this is the first potential which you are going to treat

Â you remember that I told you that, most of the time,

Â molecules which share a common space with other molecules don't see each other.

Â As opposed to stars,

Â which constantly are influenced by all other stars in the system.

Â Molecules, most of the time, just travel along straight lines.

Â They are not affected by the other molecules.

Â That's because the interaction potential of

Â the Lennard Jones model is a short range interaction model.

Â It decreases to the power six of the distance between two molecules.

Â As you can see on this graph, if you go just at a distance of

Â two to five times the radius of the molecule, the potential is almost zero.

Â Actually, it amounts to less than 1% of the potential of epsilon.

Â It becomes negligible.

Â Therefore, it is common practice when you simulate such a system to introduce

Â a cutoff length.

Â A cutoff length after which you will neglect all the other molecules,

Â because you consider their influence on the present molecule to be zero.

Â Common value of this cutoff length is a length of d equals 2.5 times sigma.

Â At which, as I said, the value of the interaction is only 1% of

Â the depth of the potential well and becomes negligible.

Â It can, of course, be another value,

Â if you want to improve the numerical accuracy of this approximation.

Â 9:11

But the cut off value, does not give you an an answer for

Â the most fundamental problem.

Â How do you actually find nearby particles?

Â How do you find particles which fall inside

Â the radius of the cutoff value of dc?

Â If you were to check all the particles to select the ones which

Â are within a reasonable range, you will need to do n operations,

Â loop all the other particles to do so.

Â You would not reduce the overall algorithmic complexity of n square

Â because for every particle, which means an operation of n,

Â you would need to check all the other particles.

Â Again an operation of order n.

Â You will again have an n square algorithm.

Â You will gain nothing.

Â You need a smart data structure, which makes it possible to quickly

Â find particles which are in the neighborhood of a given particle.

Â The solution here, is to use a grid based method, which means we take the space

Â occupied by the particles, and overlap it with a grid, which has equal-sized cells.

Â 10:42

Let's take for example the grid which has the coordinates one, two in this system,

Â and let's assume that there are five particles currently present in this cell.

Â These particles have a given ID, let's say for

Â example ID [2, 3, 7, 11 and 19].

Â Which means that when you are doing a computer simulation here, every grid

Â cell will contain a list of IDs, of particles, which are present on this grid.

Â Grid cell one, two will have a list with the values [2, 3, 7, 11, and 19].

Â We're not going to store the position and

Â the velocity of the particles inside this matrix.

Â This matrix is only here to identify particles at a given position in space.

Â We use these IDs to look up the positions and velocities in some other kind of

Â data structure Now, as before,

Â when we talk about data structures, we need to create this data structure.

Â At some point, these particles move, and whenever they move,

Â we need to reassign them to the right cell inside this grid.

Â Unfortunately, this is quite a fast preparation to perform

Â because given that a particle which has changed its position,

Â you can find out to which grid cell it is being assigned in constant-time, because

Â the space occupied by grid cells is a constant value which we know in advance.

Â We can take the particle position, and in constant time,

Â assign it to the range of a given grid cell, and

Â then add it to the list contained in the matrix an element of this grid cell.

Â Assigning all particles of a given time stat to their corresponding

Â grid position inside the matrix is a linear operation, an order n operation,

Â which is much better than an order n squared operation.

Â Once they have been assigned to the grid,

Â we can exploit this matrix to find nearby particles and

Â evaluate the forces acting on a given particle.

Â Let's take, for example, the particle which in this image is red.

Â It's the particle with the ID 11.

Â The green circle shows the distance of the cutoff length dc.

Â We will only consider the interaction of the red particle with particles

Â which are contained inside the circle.

Â To find these particles, instead of looping over all other possible particles,

Â we will use the grid to find possible candidates.

Â In this case, we just need to access the list of particles

Â of grid cell 1,1, 1,2, 2,1, and 2,2.

Â We access four grid cells, access their lists, and

Â take all the particles contained in these lists as possible candidates for

Â particles contained within the circle of cutoff length dc..

Â Once we have selected them, we need to do an additional operation to check

Â if they actually are contained within the circle, and then select them

Â to calculate the forces acting on the red particle, particle number 11.

Â 14:25

Let's assume that the single cell of our grid is larger in width

Â than the cutoff distance.

Â This means that, in the worst case, when we need to check for

Â possible dates of neighboring particles,

Â we need to check in a 2D simulation at most, nine cells.

Â The cell in which the particle is located on to which we are calculating the forces,

Â plus, it's eight neighboring cells.

Â In 3D, this would be 27 cells.

Â If we have Nc cells in total, the average number of check is n for

Â the amount of particles times nine for the neighborhood,

Â 9 N divided by Nc where the total amount of particles is divided by

Â the amount of cells, to get the average number of particles per cell.

Â If we have many cells in the system, well if the number of cells in

Â the system is of the order of the number of total particles, and

Â this is the case if the cutoff lengths is much smaller than the size of

Â the full domain, then this algorithm has a complexity of order N,

Â which means it is a linear algorithm.

Â It is an algorithm which is much more efficient than the root force and

Â square algorithm

Â