Biology Reference
In-Depth Information
m
(Fig. 6). This is done independently for each particle and can efficiently
be parallelized on vector and multi-processor computers.
32
In higher
dimensions, the kernels are tensorial products of the one-dimensional
(1D) kernels. Their values can thus be computed independently in
each spatial direction and then multiplied to form the final interpola-
tion weight for a given particle and mesh node:
W
(
x
,
y
,
z
)
=
W
x
(
x
)
W
y
(
y
)
W
z
(
z
).
Meshes are used not only to accelerate the computation of long-
range interactions in hybrid PM schemes, but also to periodically reini-
tialize the particle locations to regular positions in order to maintain the
overlap condition of Eq. (7). Reinitialization using a mesh is needed if
particles tend to accumulate in certain areas of the computational domain
and to disperse in others. In such cases, the function approximation
would cease to be well posed as soon as the condition in Eq. (7) is vio-
lated. This can be prevented by periodically resetting the particle posi-
tions to regular locations by interpolating the particle properties to the
nodes of a regular Cartesian mesh as outlined above, discarding the pres-
ent set of particles, and generating new particles at the locations of the
mesh nodes. This procedure is called remeshing.
85
6. Efficient Algorithms for Particle Methods
The evaluation of PP interactions is a key component of particle meth-
ods and PM algorithms. Equation (1), however, defines an
N
-body prob-
lem, which is of potentially
(
N
2
) complexity to solve. It is this high
computational cost that has long prevented the use of particle methods
in computational science. Fortunately, this can be circumvented and the
complexity can be reduced to
O
(
N
) in all practical cases. Together with
efficient implementations on parallel computers,
32
this makes particle
methods a competitive alternative to mesh-based methods.
If the functions
K
and
F
in Eq. (1) are local (but not necessarily com-
pact), the algorithmic complexity of the sums in Eq. (1) naturally reduces
to
O
(
N
) by considering only interactions within a certain cut-off radius
r
c
around each particle. This corresponds to short-range interactions
where only nearby neighbors of a given particle significantly contribute.
The specific value of
r
c
depends on the interaction law, i.e. the kernel
O
