Lubachevsky-Stillinger algorithm
Encyclopedia
Lubachevsky-Stillinger algorithm (LS algorithm, LSA, or LS protocol) is
a numerical procedure that simulates or imitates
a physical process of compressing an assembly
of hard particles. As the LSA may need thousands of arithmetic operations even for a few particles,
it is usually carried out on a digital computer.
involves a contracting hard boundary of the container,
such as a piston pressing against the particles. The LSA is able to simulate
such a scenario
.
However,
the LSA was originally introduced in the setting
without a hard boundary
where the virtual particles were "swelling" or expanding
in a fixed, finite virtual volume
with periodic boundary conditions
.
The absolute sizes of the particles were increasing but particle-to-particle relative sizes remained constant.
In general, the LSA can handle
an external compression and
an internal particle expansion,
both occurring simultaneously and possibly,
but not necessarily, combined with a
hard boundary.
In addition, the boundary can be mobile.
In a final, compressed, or "jammed" state,
some particles are not jammed, they are able to move
within "cages" formed by their immobile, jammed neighbors
and the hard boundary, if any.
These free-to-move particles are not an artifact,
or pre-designed, or target feature of the LSA,
but rather a real phenomenon.
The simulation revealed this phenomenon,
somewhat unexpectedly
for the authors of the LSA.
Frank H. Stillinger coined the term "rattlers"
for the free-to-move particles,
because
if one physically shakes a compressed bunch of hard
particles, the rattlers will be rattling.
In the "pre-jammed" mode
when the density of the configuration is
low and when the particles are mobile, the compression and expansion can be stopped, if so desired. Then the LSA, in effect, would be simulating a granular flow.
Various dynamics of the instantaneous collisions
can be simulated such as: with or without a full restitution,
with or without tangential friction.
Differences in masses of the particles can be taken
into account.
It is also easy and sometimes proves useful to
"fluidize" a jammed configuration,
by decreasing the sizes of all or some of the particles.
Another possible extension of the LSA is replacing
the hard collision force
potential
(zero outside the particle, infinity at or inside) with
a piece-wise constant force
potential
. The LSA
thus modified would approximately simulate
molecular dynamics
with continuous
short range particle-particle force interaction.
External force fields, such as gravitation
, can be
also introduced, as long as the inter-collision motion
of each particle can be represented
by a simple one-step calculation.
Using LSA for spherical particles of different sizes and/or for jamming in a non-commeasureable size
container proved to be a useful technique
for generating and studying micro-structures formed
under conditions of a crystallographic defect
or
a geometrical frustration
.
.
It should be added that
the original LS protocol was designed
primarily
for spheres of same or different sizes
.
Any deviation from the spherical
(or circular in two dimensions) shape, even a simplest one, when spheres are replaced with ellipsoids (or ellipses in two dimensions)
, causes thus modified LSA to slow down substantially.
But as long as the shape is spherical,
the LSA is able to handle particle assemblies
in tens to hundreds of thousands
on today's (2011) standard personal computers.
Only a very limited experience was reported
in using the LSA in dimensions higher than 3.
a granular flow.
The flow is rendered as a
discrete event simulation
,
the events being particle-particle or particle-boundary collisions.
Ideally, the calculations should have been
performed
with the infinite precision.
Then the jamming would have
occurred ad infinitum
.
In practice, the precision is finite as
is the available resolution of representing
the real numbers in the computer memory
,
for example, a double-precision resolution.
The real calculations are stopped
when inter-collision runs of the non-rattler particles
become
smaller than an explicitly or implicitly
specified small threshold.
For example, it is useless to continue
the calculations when inter-collision runs
are smaller than the roundoff error.
The LSA is efficient in the sense that
the events are processed essentially in an
event-driven
fashion, rather than in a
time-driven fashion. This means almost
no calculation
is wasted on computing or maintaining the positions and velocities
of the particles between the collisions.
Among the event-driven
algorithms intended for
the same task of simulating granular flow,
like, for example, the algorithm of D.C. Rapaport
,
the LSA is distinguished by a simpler
data structure
and data handling.
For any particle at any stage of calculations
the LSA keeps record of only two events:
an old, already processed committed event, which comprises
the committed event time stamp,
the particle state
(including position and velocity),
and, perhaps, the "partner"
which could be
another particle or boundary identification,
the one with which the particle collided in the past,
and a new event proposed for a future processing
with a similar set of parameters.
The new event is not committed.
The maximum of the committed old event times must never exceed
the minimum of the non-committed new event times.
Next particle to be examined by the algorithm has
the current minimum of new event times.
At examining the chosen particle,
what was previously the new event, is declared to be the old one
and to be committed,
whereas the next new event is being scheduled,
with its new time stamp, new state, and new partner,
if any.
As the next new event for a particle is being set,
some of the neighboring particles may update
their non-committed new events to better account for the new information.
As the calculations of the LSA progress,
the collision rates of particles may and usually do
increase.
Still the LSA successfully approaches the jamming state
as long as those rates remain comparable among all
the particles, except for the rattlers.
(Rattlers experience consistently low collision rates. This property allows one to detect rattlers.)
However,
it is possible for a few particles,
even just for a single particle,
to experience a very high collision
rate
along the approach to a certain simulated time.
The rate will be increasing without
a bound in proportion to
the rates of collisions in the rest of the particle ensemble.
If this happens,
then the simulation will be stuck in time,
it won't be able
to progress toward the state of jamming.
The stuck-in-time failure
can also occur when simulating
a granular flow,
without the particle compression
or expansion.
This failure mode was recognized
by the practitioners of granular flow
simulations
as an "inelastic collapse"
because
it often occurs in such simulations when
restitution coefficient
at collisions is low
(and hence the collisions are inelastic).
The failure is not specific to only the LSA algorithm.
Techniques to avoid the failure have
been proposed.
a fair measure of speedup in parallel
simulations. The
Time Warp
parallel simulation algorithm
by David Jefferson was advanced as a method
to simulate
asynchronous spacial interactions of fighting units
in combat models on a parallel computer.
Colliding particles models
offered similar simulation tasks with spacial interactions of particles
but
clear of the details that are non-essential for
exposing the simulation
techniques.
The speedup was presented as the ratio
of the execution time on a uniprocessor
over that
on a multiprocessor
, when executing the same
parallel Time Warp
algorithm.
Boris D. Lubachevsky noticed that
such a speedup assessment might be faulty because
executing a parallel algorithm
for a task on a uniprocessor
is not necessarily
the fastest way to perform the task
on such a machine.
The LSA was created in an
attempt to produce a faster uniprocessor
simulation
and hence to have a more fair assessment of the
parallel speedup.
Later on, a parallel simulation algorithm,
different from the Time Warp
,
was also proposed, that, when run on a uniprocessor
,
reduces to the LSA.
a numerical procedure that simulates or imitates
a physical process of compressing an assembly
of hard particles. As the LSA may need thousands of arithmetic operations even for a few particles,
it is usually carried out on a digital computer.
Phenomenology (what is being simulated)
A physical process of compression ofteninvolves a contracting hard boundary of the container,
such as a piston pressing against the particles. The LSA is able to simulate
such a scenario
.
However,
the LSA was originally introduced in the setting
without a hard boundary
where the virtual particles were "swelling" or expanding
in a fixed, finite virtual volume
with periodic boundary conditions
Periodic boundary conditions
In mathematical models and computer simulations, periodic boundary conditions are a set of boundary conditions that are often used to simulate a large system by modelling a small part that is far from its edge...
.
The absolute sizes of the particles were increasing but particle-to-particle relative sizes remained constant.
In general, the LSA can handle
an external compression and
an internal particle expansion,
both occurring simultaneously and possibly,
but not necessarily, combined with a
hard boundary.
In addition, the boundary can be mobile.
In a final, compressed, or "jammed" state,
some particles are not jammed, they are able to move
within "cages" formed by their immobile, jammed neighbors
and the hard boundary, if any.
These free-to-move particles are not an artifact,
or pre-designed, or target feature of the LSA,
but rather a real phenomenon.
The simulation revealed this phenomenon,
somewhat unexpectedly
for the authors of the LSA.
Frank H. Stillinger coined the term "rattlers"
for the free-to-move particles,
because
if one physically shakes a compressed bunch of hard
particles, the rattlers will be rattling.
In the "pre-jammed" mode
when the density of the configuration is
low and when the particles are mobile, the compression and expansion can be stopped, if so desired. Then the LSA, in effect, would be simulating a granular flow.
Various dynamics of the instantaneous collisions
can be simulated such as: with or without a full restitution,
with or without tangential friction.
Differences in masses of the particles can be taken
into account.
It is also easy and sometimes proves useful to
"fluidize" a jammed configuration,
by decreasing the sizes of all or some of the particles.
Another possible extension of the LSA is replacing
the hard collision force
Force
In physics, a force is any influence that causes an object to undergo a change in speed, a change in direction, or a change in shape. In other words, a force is that which can cause an object with mass to change its velocity , i.e., to accelerate, or which can cause a flexible object to deform...
potential
Potential
*In linguistics, the potential mood*The mathematical study of potentials is known as potential theory; it is the study of harmonic functions on manifolds...
(zero outside the particle, infinity at or inside) with
a piece-wise constant force
Force
In physics, a force is any influence that causes an object to undergo a change in speed, a change in direction, or a change in shape. In other words, a force is that which can cause an object with mass to change its velocity , i.e., to accelerate, or which can cause a flexible object to deform...
potential
Potential
*In linguistics, the potential mood*The mathematical study of potentials is known as potential theory; it is the study of harmonic functions on manifolds...
. The LSA
thus modified would approximately simulate
molecular dynamics
Molecular dynamics
Molecular dynamics is a computer simulation of physical movements of atoms and molecules. The atoms and molecules are allowed to interact for a period of time, giving a view of the motion of the atoms...
with continuous
short range particle-particle force interaction.
External force fields, such as gravitation
Gravitation
Gravitation, or gravity, is a natural phenomenon by which physical bodies attract with a force proportional to their mass. Gravitation is most familiar as the agent that gives weight to objects with mass and causes them to fall to the ground when dropped...
, can be
also introduced, as long as the inter-collision motion
of each particle can be represented
by a simple one-step calculation.
Using LSA for spherical particles of different sizes and/or for jamming in a non-commeasureable size
container proved to be a useful technique
for generating and studying micro-structures formed
under conditions of a crystallographic defect
Crystallographic defect
Crystalline solids exhibit a periodic crystal structure. The positions of atoms or molecules occur on repeating fixed distances, determined by the unit cell parameters. However, the arrangement of atom or molecules in most crystalline materials is not perfect...
or
a geometrical frustration
Geometrical frustration
In condensed matter physics, the term geometrical frustration means a phenomenon in which the geometrical properties of the crystal lattice or the presence of conflicting atomic forces forbid simultaneous minimization of the interaction energies acting at a given site.This may lead to highly...
.
.
It should be added that
the original LS protocol was designed
primarily
for spheres of same or different sizes
.
Any deviation from the spherical
(or circular in two dimensions) shape, even a simplest one, when spheres are replaced with ellipsoids (or ellipses in two dimensions)
, causes thus modified LSA to slow down substantially.
But as long as the shape is spherical,
the LSA is able to handle particle assemblies
in tens to hundreds of thousands
on today's (2011) standard personal computers.
Only a very limited experience was reported
in using the LSA in dimensions higher than 3.
Implementation (how the calculations are performed)
The state of particle jamming is achieved via simulatinga granular flow.
The flow is rendered as a
discrete event simulation
Discrete Event Simulation
In discrete-event simulation, the operation of a system is represented as a chronological sequence of events. Each event occurs at an instant in time and marks a change of state in the system...
,
the events being particle-particle or particle-boundary collisions.
Ideally, the calculations should have been
performed
with the infinite precision.
Then the jamming would have
occurred ad infinitum
Ad infinitum
Ad infinitum is a Latin phrase meaning "to infinity."In context, it usually means "continue forever, without limit" and thus can be used to describe a non-terminating process, a non-terminating repeating process, or a set of instructions to be repeated "forever," among other uses...
.
In practice, the precision is finite as
is the available resolution of representing
the real numbers in the computer memory
Computer memory
In computing, memory refers to the physical devices used to store programs or data on a temporary or permanent basis for use in a computer or other digital electronic device. The term primary memory is used for the information in physical systems which are fast In computing, memory refers to the...
,
for example, a double-precision resolution.
The real calculations are stopped
when inter-collision runs of the non-rattler particles
become
smaller than an explicitly or implicitly
specified small threshold.
For example, it is useless to continue
the calculations when inter-collision runs
are smaller than the roundoff error.
The LSA is efficient in the sense that
the events are processed essentially in an
event-driven
Event-driven
Event driven may refer to:The term event-driven refers to a methodology that focuses on events and event dependencies.Examples include:* Event-driven finite-state machine, finite-state machine where the transition from one state to another is triggered by an event or a message* Event-driven...
fashion, rather than in a
time-driven fashion. This means almost
no calculation
is wasted on computing or maintaining the positions and velocities
of the particles between the collisions.
Among the event-driven
Event-driven
Event driven may refer to:The term event-driven refers to a methodology that focuses on events and event dependencies.Examples include:* Event-driven finite-state machine, finite-state machine where the transition from one state to another is triggered by an event or a message* Event-driven...
algorithms intended for
the same task of simulating granular flow,
like, for example, the algorithm of D.C. Rapaport
,
the LSA is distinguished by a simpler
data structure
Data structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
and data handling.
For any particle at any stage of calculations
the LSA keeps record of only two events:
an old, already processed committed event, which comprises
the committed event time stamp,
the particle state
(including position and velocity),
and, perhaps, the "partner"
which could be
another particle or boundary identification,
the one with which the particle collided in the past,
and a new event proposed for a future processing
with a similar set of parameters.
The new event is not committed.
The maximum of the committed old event times must never exceed
the minimum of the non-committed new event times.
Next particle to be examined by the algorithm has
the current minimum of new event times.
At examining the chosen particle,
what was previously the new event, is declared to be the old one
and to be committed,
whereas the next new event is being scheduled,
with its new time stamp, new state, and new partner,
if any.
As the next new event for a particle is being set,
some of the neighboring particles may update
their non-committed new events to better account for the new information.
As the calculations of the LSA progress,
the collision rates of particles may and usually do
increase.
Still the LSA successfully approaches the jamming state
as long as those rates remain comparable among all
the particles, except for the rattlers.
(Rattlers experience consistently low collision rates. This property allows one to detect rattlers.)
However,
it is possible for a few particles,
even just for a single particle,
to experience a very high collision
rate
along the approach to a certain simulated time.
The rate will be increasing without
a bound in proportion to
the rates of collisions in the rest of the particle ensemble.
If this happens,
then the simulation will be stuck in time,
it won't be able
to progress toward the state of jamming.
The stuck-in-time failure
can also occur when simulating
a granular flow,
without the particle compression
or expansion.
This failure mode was recognized
by the practitioners of granular flow
simulations
as an "inelastic collapse"
because
it often occurs in such simulations when
restitution coefficient
at collisions is low
(and hence the collisions are inelastic).
The failure is not specific to only the LSA algorithm.
Techniques to avoid the failure have
been proposed.
History
The LSA was a by-product of an attempt to finda fair measure of speedup in parallel
Parallel
-Mathematics and science:* Parallel , an imaginary east-west line circling a globe* Parallel circuits, as opposed to series* Parallel * Parallel evolution* Parallel transport* Parallel of declination, used in astronomy-Computing:...
simulations. The
Time Warp
Time Warp
"The Time Warp" is a song featured in the 1973 rock musical The Rocky Horror Show and in the 1975 film adaption The Rocky Horror Picture Show, as well as a dance performed during the chorus of the song of the same name. The song is both an example and a parody of the dance song genre in which much...
parallel simulation algorithm
by David Jefferson was advanced as a method
to simulate
asynchronous spacial interactions of fighting units
in combat models on a parallel computer.
Colliding particles models
offered similar simulation tasks with spacial interactions of particles
but
clear of the details that are non-essential for
exposing the simulation
techniques.
The speedup was presented as the ratio
of the execution time on a uniprocessor
Uniprocessor
A uniprocessor system is a computer system with a single central processing unit. As more and more computers employ multiprocessing architectures, such as SMP and MPP, the term is used to refer to systems that still have only one CPU. Most desktop computers are now shipped with multiprocessing...
over that
on a multiprocessor
Multiprocessor
Computer system having two or more processing units each sharing main memory and peripherals, in order to simultaneously process programs.Sometimes the term Multiprocessor is confused with the term Multiprocessing....
, when executing the same
parallel Time Warp
Time Warp
"The Time Warp" is a song featured in the 1973 rock musical The Rocky Horror Show and in the 1975 film adaption The Rocky Horror Picture Show, as well as a dance performed during the chorus of the song of the same name. The song is both an example and a parody of the dance song genre in which much...
algorithm.
Boris D. Lubachevsky noticed that
such a speedup assessment might be faulty because
executing a parallel algorithm
Parallel algorithm
In computer science, a parallel algorithm or concurrent algorithm, as opposed to a traditional sequential algorithm, is an algorithm which can be executed a piece at a time on many different processing devices, and then put back together again at the end to get the correct result.Some algorithms...
for a task on a uniprocessor
Uniprocessor
A uniprocessor system is a computer system with a single central processing unit. As more and more computers employ multiprocessing architectures, such as SMP and MPP, the term is used to refer to systems that still have only one CPU. Most desktop computers are now shipped with multiprocessing...
is not necessarily
the fastest way to perform the task
on such a machine.
The LSA was created in an
attempt to produce a faster uniprocessor
Uniprocessor
A uniprocessor system is a computer system with a single central processing unit. As more and more computers employ multiprocessing architectures, such as SMP and MPP, the term is used to refer to systems that still have only one CPU. Most desktop computers are now shipped with multiprocessing...
simulation
and hence to have a more fair assessment of the
parallel speedup.
Later on, a parallel simulation algorithm,
different from the Time Warp
Time Warp
"The Time Warp" is a song featured in the 1973 rock musical The Rocky Horror Show and in the 1975 film adaption The Rocky Horror Picture Show, as well as a dance performed during the chorus of the song of the same name. The song is both an example and a parody of the dance song genre in which much...
,
was also proposed, that, when run on a uniprocessor
Uniprocessor
A uniprocessor system is a computer system with a single central processing unit. As more and more computers employ multiprocessing architectures, such as SMP and MPP, the term is used to refer to systems that still have only one CPU. Most desktop computers are now shipped with multiprocessing...
,
reduces to the LSA.
External links
- LSA in action. A collection of animations by Alexander Donev
- Source C++ codes of a version of the LSA in arbitrary dimensions
- Volume fluctuation distribution in granular packs studied using the LSA
- LSA generalized for particles of arbitrary shape
- LSA used for production of representative volumes of microscale failures in packed granular materials