Biology Reference
In-Depth Information
Another point of possible optimization concerns the symmetry of PP
interactions. By construction of the kernel-based interactions, the effect
of a particle
p
on another particle
q
is the same (with a possible sign
change) as the effect of particle
q
on
p
. Looping over all particles and
computing the interactions with all neighbors within the cut-off radius
thus considers every interaction twice. The computational cost can be
reduced by a factor of (at most) two if interactions are evaluated sym-
metrically. We then only loop over half of the neighbors and attribute the
interaction contributions to both participating particles at once. How,
then, is it possible to make sure that all interactions are considered exactly
once? In cell lists, it is sufficient to loop over only those particles
q
in the
center cell for which
q
p
, as well as over all particles in half of the neigh-
boring cells [Fig. 7(b)]. In Fig. 7(c), diagonal interactions are introduced
in order to further reduce the memory overhead for the boundary layers
by 33% in the 2D case and 40% in the 3D case.
32
In parallel implementa-
tions, the diagonal interaction scheme moreover has the advantage of
lower communication overhead. If the cells are numbered in ascending
x
,
y
,(
z
), starting from the center cell with number 0, the symmetric cell-
cell interactions are
32
0-0, 0-1, 0-3, 0-4, and 1-3 in the 2D case; and
0-0, 0-1, 0-3, 0-4, 0-9, 0-10, 0-12, 0-13, 1-3, 1-9, 1-12, 3-9, 3-10,
and 4-9 in the 3D case. Verlet list algorithms remain unchanged in
the symmetric case, as the Verlet lists are constructed using interme-
diate symmetric cell lists and hence only contain unique interactions in
the first place.
>
6.2. Fast Algorithms for Long-Range Interactions
In 1986, Joshua Barnes and Piet Hut
113
introduced a fast hierarchical
O
(
N
log
N
) algorithm for
N
-body problems. The Barnes-Hut algorithm
divides the domain into a tree of regular cuboidal cells. Each cell in the
tree has half the edge length of its parent cell, and stores information
about the center of mass and the total strength of all particles inside. The
tree is then traversed for each particle
p
for which the interactions are to be
evaluated. Direct PP interactions are only computed for nearby interaction
partners
q
. If the partners are sufficiently far away, they are collectively
