Lubachevsky–Stillinger algorithm

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.
Using a variant of Lubachevsky-Stillinger algorithm, 1000 congruent isosceles triangles are randomly packed by compression in a rectangle with periodic (wrap-around) boundary. The rectangle which is the period of pattern repetition in both directions is shown. Packing density is 0.8776

Phenomenology

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] However, the LSA was originally introduced in the setting without a hard boundary[2][3] 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[4] or a geometrical frustration[5][6] It should be added that the original LS protocol was designed primarily for spheres of same or different sizes.[7]

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),[8] 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[9] in using the LSA in dimensions higher than 3.
Implementation

The state of particle jamming is achieved via simulating 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,[10] 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" [11] 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.[12]
History

The LSA was a by-product of an attempt to find 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.[13] Colliding particles models[14] 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.[15]
References

F. H. Stillinger and B. D. Lubachevsky, Crystalline-Amorphous Interface Packings for Disks and Spheres, J. Stat. Phys. 73, 497-514 (1993)
B. D. Lubachevsky and F. H. Stillinger, Geometric properties of random disk packings, J. Statistical Physics 60 (1990), 561-583 http://www.princeton.edu/~fhs/geodisk/geodisk.pdf
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
F. H. Stillinger and B. D. Lubachevsky. Patterns of Broken Symmetry in the Impurity-Perturbed Rigid Disk Crystal, J. Stat. Phys. 78, 1011-1026 (1995)
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
Boris D. Lubachevsky, Ron L. Graham, and Frank H. Stillinger, Spontaneous Patterns in Disk Packings. Visual Mathematics, 1995. http://vismath5.tripod.com/lub/
A.R. Kansal, S. Torquato, and F.H. Stillinger, Computer Generation of Dense Polydisperse Sphere Packings, J. Chem. Phys. 117, 8212-8218 (2002) http://cat.inist.fr/?aModele=afficheN&cpsidt=13990882
A. Donev, F.H. Stillinger, P.M. Chaikin, and S. Torquato, Unusually Dense Crystal Packings of Ellipsoids, Phys. Rev. Letters 92, 255506 (2004)
M. Skoge, A. Donev, F.H. Stillinger, and S. Torquato, Packing Hyperspheres in High-Dimensional Euclidean Spaces, Phys. Rev. E 74, 041127 (2006)
D.C. Rapaport, The Event Scheduling Problem in Molecular Dynamic Simulation, Journal of Computational Physics Volume 34 Issue 2, 1980
S. McNamara, and W.R. Young, Inelastic collapse in two dimensions, Physical Review E 50: pp. R28-R31, 1994
John J. Drozd, Computer Simulation of Granular Matter: A Study of An Industrial Grinding Mill, Thesis, Univ. Western Ontario, Canada, 2004. http://imaging.robarts.ca/~jdrozd/thesisjd.pdf
F. Wieland, and D. Jefferson, Case studies in serial and parallel simulations, Proc. 1989 Int'l Conf. Parallel Processing, Vol.III, F. Ris, and M. Kogge, Eds., pp. 255-258.
P. Hontales, B. Beckman, et al., Performance of the colliding pucks simulation of the Time Warp operating systems, Proc. 1989 SCS Multiconference, Simulation Series, SCS, Vol. 21, No. 2, pp. 3-7.

B.D. Lubachevsky, Simulating Billiards: Serially and in Parallel, Int.J. in Computer Simulation, Vol. 2 (1992), pp. 373-411.

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

Physics Encyclopedia