Lubachevsky-Stillinger (compression) 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.
A physical process of compression often
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 [1]
[2] .
However,
the LSA was originally
introduced [3]
[4]
in the setting with
periodic boundary conditions
where the virtual particles were "swelling" or expanding
in a fixed, finite virtual volume without hard boundary.
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
combined with a present or
absent hard boundary.
In a final, compressed, or "jammed" state,
some particles, the so-called "rattlers," are not jammed, they are able to move
within "cages" formed by their immobile, jammed neighbors
and the boundary, if any.
A substantial limitation of the original LS protocol
is that it was designed to practically work only
for spherical particles, though the spheres may be
of different sizes
[5].
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)
[6]
, causes thus modified LSA to slow down dramatically
[7] .
But as long as the shape is spherical,
the LSA is able to handle particle ensembles
in tens to hundreds of thousands
on today's (2011) standard personal computers.
Only a very limited experience was reported
[8]
in using the LSA in dimensions higher than 3.
Comments on the algorithm
Particle jamming in LSA is achieved via simulating pre-jammed
granular flow.
The flow is rendered as a
discrete event simulation,
the events being particle-particle or particle-boundary collisions
with jamming ideally occurring after infinitely many
collisions and infinitely lengthy calculations.
In practice, the calculations are finite,
they are stopped
when inter-collision particle runs (except those for the
rattlers) become
smaller than an explicitly specified small threshold
or when they become smaller than an implicit threshold,
such as a threshold implied
by the computing resolution (for example, by the
double precision resolution).
The key to the algorithm efficiency is that
the calculations are done essentially in an
event-driven fashion, rather than in a
time-driven fashion. This means that almost
no computation
is wasted on calculating 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 Rapaport
Cite error: There are <ref> tags on this page without content in them (see the help page).
the LSA is distinguished by a simpler data structure
and data handling.
For any particle at any stage of calculations
the LSA maintains the record of only two events:
an old, already processed event, which comprises
the processed event time stamp,
the particle state (including
position and velocity), and, perhaps,
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.
Examples of use
References
- ^ Boris D. Lubachevsky and Frank H. Stillinger, Epitaxial frustration in deposited packings of rigid disks and spheres. Physical Review E 70:44, 41604 (2004) http://arxiv.org/PS_cache/cond-mat/pdf/0405/0405650v5.pdf
- ^ Crystalline-Amorphous Interface Packings for Disks and Spheres, F. H. Stillinger and B. D. Lubachevsky, J. Stat. Phys. 73, 497-514 (1993)
- ^ B. D. Lubachevsky and F. H. Stillinger, Geometric properties of random disk pack- ings, J. Statistical Physics 60 (1990), 561-583
- ^ B.D. Lubachevsky, How to Simulate Billiards and Similar Systems, Journal of Computational Physics Volume 94 Issue 2, May 1991 http://arxiv.org/PS_cache/cond-mat/pdf/0503/0503627v2.pdf
- ^ Computer Generation of Dense Polydisperse Sphere Packings, A.R. Kansal, S. Torquato, and F.H. Stillinger, J. Chem. Phys. 117, 8212-8218 (2002)
- ^ Unusually Dense Crystal Packings of Ellipsoids, A. Donev, F.H. Stillinger, P.M. Chaikin, and S. Torquato, Phys. Rev. Letters 92, 255506 (2004)
- ^ http://www.pack-any-shape.com
- ^ Packing Hyperspheres in High-Dimensional Euclidean Spaces," M. Skoge, A. Donev, F.H. Stillinger, and S. Torquato, Phys. Rev. E 74, 041127 (2006)