Biology Reference
In-Depth Information
functions
K
and
F
in Eq. (1), and has to be chosen to meet the desired
simulation accuracy. The most conservative choice of
r
c
is given by the
radius where the interaction contributions fall below the machine epsilon
of the computer
84
and hence become insignificant.
For long-range interactions whose value decays as
(1/
r
2
) or slower
with increasing interparticle distance
r
, cut-offs are not appropriate and
we have to consider the full
N
-body problem of Eq. (1). Examples of
such interactions include Coulomb forces, gravitation, or the Biot-Savart
law in electromagnetism and fluid dynamics. Fast algorithms such as mul-
tipole expansions
110
(cf. Sec. 6.2) are, however, available to reduce the
complexity of the corresponding pure particle method to
O
(
N
) also in
these cases, albeit with a large prefactor. This large prefactor typically
causes pure particle implementations of long-range interactions to be
several orders of magnitude slower than the corresponding hybrid PM
algorithm. Nevertheless, fast
N
-body methods are appealing from a
conceptual point of view.
O
6.1. Fast Algorithms for Short-Range Interactions
Considering only the interactions within an
r
c
-neighborhood naturally
reduces the algorithmic complexity of the PP evaluation from
O
(
N
2
) to
O
(
N
) with a prefactor that depends on the value of
r
c
and the local par-
ticle density. This requires, however, that the set of neighbors to interact
with is known or can be determined with at most
(
N
) cost. Since par-
ticle methods do not use any connectivity information (cf. Sec. 4.4),
neighborhood information is not explicitly available and it changes over
time if particles move. Finding the neighbors of each particle by search-
ing over all other particles would again render the complexity of the algo-
rithm
O
(
N
2
), annihilating all benefits of a finite cut-off radius
r
c
. Two
standard methods are available to find the interaction partners in
O
O
(
N
)
time: cell lists and Verlet lists.
In cell lists, particles are sorted into equisized cubic cells whose size
corresponds to the interaction cut-off
r
c
. Each cell contains a (linked) list
of the particles residing in it. Interactions are then computed by sweep-
ing through these lists. If particle
p
is to interact with all of its neighbors
closer than
r
c
, this involves considering all other particles in the same cell
