Wikipedia

Lubachevsky–Stillinger algorithm

This is an old revision of this page, as edited by Lsalgo (talk | contribs) at 04:10, 26 April 2011. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.


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.

Phenomenology (what is being simulated)

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 possibly, but not necessarily, combined with a hard boundary, and the boundary can be mobile. 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.

In the pre-"jammed" mode when the density of the particles is low and when they are mobile, the compression and expansion can be stopped, if so desired, and then the LSA, in effect, would be simulating dynamic granular flow. Various dynamics of the instantaneous collisions can be simulated: with or without a full restitution, with or without tangential friction, and so on. Differences in particles' masses can be taken into account. It is also easy and sometimes proves useful to un-"jam" or "fluidize" the configuration, by decreasing the sizes of all or some of the particles. Another possible extension of the LSA is replacing the hard collision potential (zero outside the particle, infinity at or inside) with a piece wise constant potential. Thus modified LSA would approximate a molecular dynamic simulation 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.

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. 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 [7] in using the LSA in dimensions higher than 3.

Implementation (how the calculations are performed)

The state of particle jamming is achieved via simulating 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.

The LSA is efficient in the sense that the event are processed essentially in an event-driven fashion, rather than in a time-driven fashion. This means that 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 Rapaport [8] , 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, 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. At processing the scheduled event for a particle, what was previously the new event, is declared to be the old one, whereas the next new event is being scheduled, with its new time stamp, new state, and new partner.

As the calculations of the LSA progress, the collision rates of particles may and usually do increase without a bound. Still the LSA successfully achieves the jamming state as long as those rates remains comparable among most particles (except the rattlers, those experience low collision rates). However, a possibility exists that along the approach to a certain simulated time, a small fraction of the particle ensemble, even a single particle, would exhibit an ever increasing collision rate not only in the absolute terms, but also as compared with the rates of collisions in the rest of the ensemble. Then the simulation might not be able to advance beyond this simulated time, even though the process of jamming would not be close to its completeness on the approach to such a time.

The "stuck in time" failure can also occur when using the LSA just for simulating a granular flow, without the particle compression or expansion. This failure mode, not necessarily attributed only to the LSA, but that exists in the area of granular flow simulations at large, has been recognized by some practitioners as an "inelastic collapse" [9] because it often occurs in hard particle granular flow simulations when restitution coefficient at collisions is low. Techniques to avoid the failure have been proposed.

Examples of use

References

  1. ^ 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
  2. ^ Crystalline-Amorphous Interface Packings for Disks and Spheres, F. H. Stillinger and B. D. Lubachevsky, J. Stat. Phys. 73, 497-514 (1993)
  3. ^ B. D. Lubachevsky and F. H. Stillinger, Geometric properties of random disk pack- ings, J. Statistical Physics 60 (1990), 561-583
  4. ^ 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
  5. ^ Computer Generation of Dense Polydisperse Sphere Packings, A.R. Kansal, S. Torquato, and F.H. Stillinger, J. Chem. Phys. 117, 8212-8218 (2002)
  6. ^ Unusually Dense Crystal Packings of Ellipsoids, A. Donev, F.H. Stillinger, P.M. Chaikin, and S. Torquato, Phys. Rev. Letters 92, 255506 (2004)
  7. ^ Packing Hyperspheres in High-Dimensional Euclidean Spaces," M. Skoge, A. Donev, F.H. Stillinger, and S. Torquato, Phys. Rev. E 74, 041127 (2006)
  8. ^ D.C. Rapaport, The Event Scheduling Problem in Molecular Dynamic Simulation, Journal of Computational Physics Volume 34 Issue 2, 1980
  9. ^ McNamara, S. and Young, W. R., Inelastic collapse in two dimensions, Physical Review E 50: pp. R28-R31, 1994
Retrieved from "https://en.wikipedia.org/w/index.php?title=Lubachevsky–Stillinger_algorithm&oldid=425952458"