Lubachevsky–Stillinger algorithm
Lubachevsky Stillinger algorithm (LS algorithm, LSA,
or LS protocol) sometimes also called Lubachevsky Stillinger compression algorithm (or protocol) is
a numerical procedure that simulates or imitates
a physical process of compressing an assembly
of hard particles. The LSA may need thousands of arithmetic operations even for a few particles
and so it is usually carried on a digital computer.
A real physical process of compression typically
(but not always) involves a contracting container
boundary, such as a piston pressing against the particles, and the LSA is able to simulate just
such a scenario.
However,
in a more frequently used setting the LSA compresses
the virtual particles by "swelling" or expanding them
in a fixed limited virtual volume.
The absolute sizes of particles are increasing but particle-to-particle relative sizes remain constant.
As a result, in a final, compressed, or "jammed" state,
some particles, the so-called "rattlers," turn out not to be jammed. Rattlers are mobile
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. 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 dramatically.
But as long as the shape is spherical,
the LSA is able to handle tens to hundreds of thousands
of particles
on a standard personal computer of today.