246 Molecular dynamics simulations
N
N
NN
N
N
N
N
IIII
I
I
I
II
I II
I
I
I
II
I
I
I
II
II
II
I
S
Figure 8.7. Interaction list of a squareSat leveln. The squares at levelnare
separated by thin lines, their parents (at leveln−1) by heavy lines. For the square
labelled by S, the squares in the interaction list of a square are denoted by I. The
nearest neighbours are labelled by N.
squares might be very close so that the multipole expansion would require far too
many terms. These squares will be dealt with at a higher level, so we apply this
approximation in each step to at least next nearest squares and skip squares lying in
regions that have been treated at previous levels. Therefore, the squares with which
the particles inSwill interact at the present level are those (1) which are not nearest
neighbours ofSand (2) whose parent was a nearest neighbour of the parent ofS.
These squares form theinteraction listofS. Figure 8.7 shows which squares are in
the interaction list ofS. It will be clear that all the interactions will be taken into
account when proceeding in this way.
More specifically, at levelnwe carry out two steps.
- We calculate the multipole moments of each square of the present level.
- For each particle, we calculate the interactions with the interaction list of the
square to which it belongs using the multipole expansion for the particles in the
cells.
This process is carried through overnmax=(log 2 N)/2 steps so that forNbeing an
integer power of 4, the squares at the lowest level contain on average one particle.
Empty squares are ‘pruned’ from the tree, that is, they are not divided up any more.
Let us now calculate the number of steps needed in this procedure. We assume that
we carry out the multipole expansion up to orderM. This number is independent of
the number of particlesN.Atleveln, the first step, in which the multipole moments
are calculated, requiresN×Msteps. The second step requiresN×M×Ksteps,
