Lubachevsky–Stillinger algorithm: Difference between revisions

Revision as of 19:14, 30 September 2019

Revision as of 04:11, 4 December 2019

Line 1:

{{Short description|computational physics simulation algorithm}}

'''Lubachevsky-Stillinger (compression) algorithm''' (LS algorithm, LSA, or LS protocol) is a numerical procedure suggested by [[F. H. Stillinger]] and B.D. Lubachevsky that simulates or imitates a physical process of compressing an assembly of hard particles.<ref name="StillingerLubachevskyJStat">B.{{cite Djournal|doi=10. Lubachevsky and F1007/bf01025983|url=https://www. Hprinceton. Stillinger, edu/~fhs/geodisk/geodisk.pdf|title=Geometric properties of random disk packings,|journal=Journal J.of Statistical Physics |volume=60 (|issue=5–6|pages=561–583|year=1990),|last1=Lubachevsky|first1=Boris 561-583D.|last2=Stillinger|first2=Frank http://wwwH.princeton|bibcode=1990JSP.edu/~fhs/geodisk/geodisk.pdf..60..561L}}</ref> As the LSA may need thousands of arithmetic operations even for a few particles, it is usually carried out on a computer.[[File:1000 triangles packed in rectangle.png|thumb|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.<ref>F.{{cite Hjournal|doi=10. Stillinger and B. D. Lubachevsky, 1007/bf01054337|title=Crystalline-Amorphousamorphous Interfaceinterface Packingspackings for Disksdisks and Spheres,spheres|journal=Journal J.of Stat. Phys.Statistical Physics|volume=73,|issue=3–4|pages=497–514|year=1993|last1=Stillinger|first1=Frank 497-514H.|last2=Lubachevsky|first2=Boris (1993)D.}}</ref> However, the LSA was originally introduced in the setting without a hard boundary<ref name="StillingerLubachevskyJStat"/><ref>B{{cite journal|doi=10.D. Lubachevsky, 1016/0021-9991(91)90222-7|title=How to Simulatesimulate Billiardsbilliards and Similar Systems,similar systems|journal=Journal of Computational Physics Volume |volume=94 Issue |issue=2, May |pages=255–283|year=1991|last1=Lubachevsky|first1=Boris https://arxivD.org/PS_cache/|bibcode=1991JCoPh..94..255L|arxiv=cond-mat/pdf/0503/0503627v2.pdf0503627}}</ref> 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.

Line 10:

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]]<ref>F.{{cite Hjournal|doi=10. Stillinger and B. D. Lubachevsky. 1007/bf02183698|title=Patterns of Brokenbroken Symmetrysymmetry in the Impurityimpurity-Perturbedperturbed Rigidrigid-disk Diskcrystal|journal=Journal Crystal,of J.Statistical StatPhysics|volume=78|issue=3–4|pages=1011–1026|year=1995|last1=Stillinger|first1=Frank H.|last2=Lubachevsky|first2=Boris PhysD.|bibcode=1995JSP.... 78, 1011-1026 (1995).1011S}}</ref> or a [[geometrical frustration]]<ref>Boris{{cite Djournal|doi=10. Lubachevsky and Frank H1103/physreve.70. Stillinger, 041604|pmid=15600418|title=Epitaxial frustration in deposited packings of rigid disks and spheres. |journal=Physical Review E |volume=70:44, 41604 (|issue=4|pages=041604|year=2004)|last1=Lubachevsky|first1=Boris https://arxivD.org/PS_cache/|last2=Stillinger|first2=Frank H.|bibcode=2004PhRvE..70d1604L|arxiv=cond-mat/pdf/0405/0405650v5.pdf0405650}}</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.{{cite Kansal, Sjournal|doi=10. Torquato, and F1063/1.H. Stillinger, 1511510|title=Computer Generationgeneration of Densedense Polydispersepolydisperse Spheresphere Packings,packings|journal=The J.Journal Chem.of Phys.Chemical Physics|volume=117, 8212-8218 (|issue=18|pages=8212–8218|year=2002)|last1=Kansal|first1=Anuraag http://cat.inistR.fr/?aModele|last2=afficheN&cpsidtTorquato|first2=13990882Salvatore|last3=Stillinger|first3=Frank H.|bibcode=2002JChPh.117.8212K}}</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.{{cite Donev, Fjournal|doi=10.H1103/physrevlett. Stillinger, P92.M. Chaikin, and S. Torquato, 255506|pmid=15245027|title=Unusually Dense Crystal Packings of Ellipsoids, |journal=Physical Review Letters |volume=92, |issue=25|pages=255506|year=2004|last1=Donev|first1=Aleksandar|last2=Stillinger|first2=Frank (2004)H.|last3=Chaikin|first3=P. M.|last4=Torquato|first4=Salvatore|bibcode=2004PhRvL..92y5506D|arxiv=cond-mat/0403286}}</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.{{cite Skoge, Ajournal|doi=10. Donev, F1103/physreve.H74. Stillinger, and S. Torquato, 041127|pmid=17155042|title=Packing Hypersphereshyperspheres in Highhigh-Dimensionaldimensional Euclidean Spaces,spaces|journal=Physical Phys. Rev.Review E |volume=74, |issue=4|pages=041127|year=2006|last1=Skoge|first1=Monica|last2=Donev|first2=Aleksandar|last3=Stillinger|first3=Frank (2006)H.|last4=Torquato|first4=Salvatore|bibcode=2006PhRvE..74d1127S|arxiv=cond-mat/0608362}}</ref>

in using the LSA in dimensions higher than 3.

Line 22:

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 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 programming|event-driven]] algorithms intended for the same task of simulating [[granular flow]], like, for example, the algorithm of D.C. Rapaport,<ref>D{{cite journal|doi=10.C. Rapaport, 1016/0021-9991(80)90104-7|title=The Eventevent Schedulingscheduling Problemproblem in Molecularmolecular Dynamic Simulation,dynamic simulation|journal=Journal of Computational Physics Volume |volume=34 Issue |issue=2, |pages=184–201|year=1980|last1=Rapaport|first1=D.C|bibcode=1980JCoPh..34..184R}}</ref> 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.

Line 33:

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 particle compression or expansion. This failure mode was recognized by the practitioners of granular flow simulations as an "inelastic collapse" <ref>S. McNamara, and{{cite Wjournal|doi=10.R1103/physreve. Young, 50.r28|pmid=9962022|title=Inelastic collapse in two dimensions, |journal=Physical Review E |volume=50: pp|issue=1|pages=R28–R31|year=1994|last1=McNamara|first1=Sean|last2=Young|first2=W. R28-R31, 1994R.|bibcode=1994PhRvE..50...28M}}</ref> because it often occurs in such simulations when the [[restitution coefficient]] in collisions is low (i.e. 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. {{cite web |url=http://imaging.robarts.ca/~jdrozd/thesisjd.pdf |title=Archived copy |accessdate=2011-05-25 |url-status=dead |archiveurl=https://web.archive.org/web/20110818102135/http://imaging.robarts.ca/~jdrozd/thesisjd.pdf |archivedate=2011-08-18 }}</ref>

== History ==