Biology Reference
In-Depth Information
Fig. 7.
Cell-cell interactions in cell list algorithms. (a) For asymmetric PP interac-
tions, all adjacent cells have to be considered and the interactions are one-sided.
(b) In traditional symmetric cell list algorithms, interactions are required on all but
one boundary. (c) Introducing diagonal interactions (1-3), the cell layers for the
boundary conditions (light blue; cf. Sec. 7.2.2) also become symmetric. This reduces
the memory overhead and improves the efficiency of parallel implementations by
reducing the communication volume. The 2D case is depicted. See text for interac-
tions in the 3D case.
as particle
p
(center cell) as well as all particles in all immediately adjacent
cells [Fig. 7(a)]. The shaded areas around the computational domain in
Fig. 7 are needed to satisfy the boundary conditions using the method of
images as outlined in Sec. 7.2.2.
For spherically symmetric interactions in 3D, cell lists contain up to
27/(4
π
≈
6 times more particles than actually needed. Verlet lists
111
are available to reduce this overhead. For each particle
p
, they consist of
an explicit list of all other particles with which it has to interact. This list
contains the indices of all particles within a sphere around
x
p
. The radius
of this Verlet sphere has to be at least
r
c
, but is usually enlarged by a cer-
tain margin (skin) in order for the Verlet lists to be valid over several sim-
ulation time steps. The Verlet lists need to be rebuilt as soon as any
particle has moved farther than the skin margin. Choosing the skin size
is a trade-off between minimizing the lengths of the lists (and hence the
number of interactions to be computed) and maximizing the time
between list updates.
112
In the 3D case, Verlet list algorithms are at most
81/(4
/3)
π
(1
+
skin)
3
) times faster than cell list algorithms. In order to ensure
overall
O
(
N
) scaling, Verlet lists are constructed using intermediate
cell lists.
