8.7 Long-range interactions 245...........
Figure 8.6. Hierarchical subdivision of the full simulation space (a square) into
children, grandchildren etc.such that the short range force vanishes beyond some small range, and the long
range force can be calculated accurately on the grid. The splitting can be obtained
by considering the long range force as resulting from a particle whose charge
(or mass) is distributed over some finite range (homogeneous sphere, Gaussian
distribution, ...). The short range force is then the potential resulting from the
difference between the point charge and the finite-width distribution (cf. the Ewald
method). The long range interactions are treated as in the PM method, and the
short range ones can be dealt with using the PP scheme. The resulting method is
called theparticle–particle/particle–mesh(PPPM) or P^3 M method. For a detailed
descriptionofthePMandPPPMmethods,seeRef. [19].
We now describe thetree-codealgorithm in some detail [ 57 – 60 ]. The amount of
computer time involved in the evaluation of the forces in this method is reduced to
O(NlnN)steps. We describe the Barnes–Hut[ 57 ] version in the formulation by van
Dommelen and Rundensteiner [ 61 , 62 ] and restrict ourselves to two-dimensional
gravitational (or Coulomb) systems, with an interaction lnrbetween two particles
of unit mass (or charge) and separationr. The idea of the method is that the force
which a mass experiences from a distant cluster of particles can be calculated from
a multipole expansion of the cluster. The convergence of the multipole expansion
depends on the ratio of the distance from the cluster and its linear size.
The total system volume is hierarchically divided up into blocks. We start with
a square shape (level 0) which in a first step is divided into four squares of half the
linear size (level 1), and at the next step each of these squares is divided up into four
smaller ones etc. We speak of parents and children of squares in this hierarchy –
seeFigure 8.6. Now consider some squareSat leveln. It is not justified to apply
the multipole expansion to nearest neighbour squares as particles in neighbouring