Asynchronous Event-Driven Particle Algorithms Page: 3 of 12
This article is part of the collection entitled: Office of Scientific & Technical Information Technical Reports and was provided to Digital Library by the UNT Libraries Government Documents Department.
The following text was automatically extracted from the image on this page using optical character recognition software:
Asynchronous Event-Driven Particle Algorithms
Lawrence Livermore National Laboratory, P.O.Box 808, Livermore, CA 94551-9900
1st March 2007
We present in a unifying way the main components of
three examples of asynchronous event-driven algorithms for
simulating physical systems of interacting particles. The
first example, hard-particle molecular dynamics (MD), is
well-known. We also present a recently-developed diffusion
kinetic Monte Carlo (DKMC) algorithm, as well as a novel
event-driven algorithm for Direct Simulation Monte Carlo
(DSMC). Finally, we describe how to combine MD with
DSMC in an event-driven framework, and discuss some
promises and challenges for event-driven simulation of re-
alistic physical systems.
There is a wide range of particle systems from com-
putational science problems that are best simulated us-
ing asynchronous event-driven (AED) algorithms. Ex-
amples include: molecular dynamics (MD) for systems
of hard particles [18, 3] such as disordered packings ,
granular materials , colloids [8, 15] and particle-laden
flows ; kinetic Monte Carlo (KMC)  simulation
of diffusion-limited reactions (DKMC)  such as nu-
cleation, growth, and coarsening during epitaxial growth
, diffusion quantum Monte Carlo , nuclear reactions
, bio-chemical reactions , and self-assembly of
nano-structures ; direct simulation Monte Carlo (DSMC)
 for micro hydrodynamics , granular flows , and
plasma flows ; contact dynamics for modeling sys-
tems of rigid bodies computer graphics ; and many
others. As of yet unexplored are multi-scale and multi-
physics algorithms such as combined flow and diffusion
with (bio)chemical reactions.
In this work we will focus on a class of particle-based
problems that are very common in computational materials
science and are well-suited for AED simulation. Specif-
ically, we will focus on the simulation of large systems of
mobile particles interacting with short-range pairwise (two-
body) potentials (forces). Our goal will be to reveal the
common building blocks of these simulations (e.g., event
*This work was performed under the auspices of the U.S. Department
of Energy by the University of California Lawrence Livermore National
Laboratory under Contract No. W-7405-Eng-48.
queues, neighbor searches), but also to highlight the com-
ponents that are problem specific (e.g., event prediction and
processing). We will present these components in some de-
tail for three specific examples: hard-particle MD, DKMC,
and DSMC. Through the discussion of these examples we
will demonstrate the undeniable advantages of AED algo-
rithms, but we will also reveal the difficulties with using
AED algorithms for realistic models.
We consider the simulation of the time evolution of a
collection of N interacting particles in d-dimensions start-
ing from some initial condition. At any point in time, the
system Q (Q, B) is characterized by the configuration
Q (qi, ... , qN), containing at least the centroid posi-
tions r, for every particle i, and the additional global in-
formation B, which may involve variables such as bound-
ary conditions or external fields. The number of particles
N may also vary with time. For each particle i we may
consider an arbitrary number of attributes in addition to
the position of the centroid, for example, q may also con-
tain the linear and/or angular velocity, the orientation and/or
the chemical specie (shape, charge, mass, internal compo-
sition) of particle i. Typically each particle configuration
q, will at least contain an integer that identifies its specie
1 < s, < Ns, and some information will be shared among
all particles belonging to the same specie (ex., the charge
or mass). In particular, the symmetric interaction table Z,,
stores NS(NS+1)/2 logical (true or false) entries that spec-
ify whether species a and ) interact or not.
Two particles i and j are overlapping only if a certain
(generalized) distance between them dig (q, q) > 0 is less
than some cutoff distance or diameter D23. Overlapping
particles react with each other in an application specific
manner. Typically the type of reaction and D2; depends
(only) on the species of the two particles and D,, but there
may also be dependencies on time or some other external
field parameters. For example, for (additive) hard spheres
Dig =(D, + D )/2 and the type of reaction is (hard-core)
repulsion. For a non-interacting pair of particles one may
set Di= 0. Particles may also overlap with boundaries
of the simulation domain, such as hard walls or reactive
surfaces, however, typically the majority of interactions are
Here’s what’s next.
This article can be searched. Note: Results may vary based on the legibility of text within the document.
Tools / Downloads
Get a copy of this page or view the extracted text.
Citing and Sharing
Basic information for referencing this web page. We also provide extended guidance on usage rights, references, copying or embedding.
Reference the current page of this Article.
Donev, A. Asynchronous Event-Driven Particle Algorithms, article, February 28, 2007; Livermore, California. (https://digital.library.unt.edu/ark:/67531/metadc877461/m1/3/: accessed April 18, 2019), University of North Texas Libraries, Digital Library, https://digital.library.unt.edu; crediting UNT Libraries Government Documents Department.