Lubachevsky–Stillinger algorithm: Difference between revisions

Revision as of 00:32, 17 June 2016

Revision as of 16:40, 10 September 2017

Line 15:

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]]<ref>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)</ref> or a [[geometrical frustration]]<ref>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</ref><ref>Boris D. Lubachevsky, Ron L. Graham, and Frank H. Stillinger, Spontaneous Patterns in Disk Packings. Visual Mathematics, 1995. http://vismath5.tripod.com/lub/</ref> It should be added that the original LS protocol was designed primarily for spheres of same or different sizes.<ref>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</ref>

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),<ref>A. Donev, F.H. Stillinger, P.M. Chaikin, and S. Torquato, Unusually Dense Crystal Packings of Ellipsoids, Phys.Physical Rev.Review Letters 92, 255506 (2004)</ref> 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<ref>M. Skoge, A. Donev, F.H. Stillinger, and S. Torquato, Packing Hyperspheres in High-Dimensional Euclidean Spaces, Phys. Rev. E 74, 041127 (2006)</ref>

Line 23:

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 programming|event-driven]] fashion, rather than in a

Line 37:

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" <ref>S. McNamara, and W.R. Young, Inelastic collapse in two dimensions, Physical Review E 50: pp. R28-R31, 1994</ref> 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.<ref> 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 </ref>

== History ==

The LSA was a by-product of an attempt to find a fair measure of [[speedup]] in [[Parallel algorithm|parallel]] [[simulations]]. The [[Time Warp (algorithm)|Time Warp]] parallel simulation algorithm by David Jefferson was advanced as a method to simulate asynchronous spatial interactions of fighting units in combat models on a [[parallel computer]].<ref>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. </ref> Colliding particles models<ref>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. </ref> offered similar simulation tasks with spatial 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.<ref>B.D. Lubachevsky, Simulating Billiards: Serially and in Parallel, Int.J. in Computer Simulation, Vol. 2 (1992), pp. 373-411.</ref>

Line 55:

* [http://www.pack-any-shape.com/ LSA generalized for particles of arbitrary shape]

* [http://onlinelibrary.wiley.com/doi/10.1002/pamm.200610180/pdf LSA used for production of representative volumes of microscale failures in packed granular materials]

<!--- Categories --->

{{DEFAULTSORT:Lubachevsky-Stillinger Algorithm}}

<!--- Categories --->

[[Category:Computational physics]]

[[Category:Scientific modeling]]