Content deleted Content added
m Removing from Category:Articles created via the Article Wizard using Cat-a-lot |
short desc |
||
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. 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</ref>
==Phenomenology==
Line 6 ⟶ 7:
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.
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.C. Rapaport, The Event Scheduling Problem in Molecular Dynamic Simulation, Journal of Computational Physics Volume 34 Issue 2, 1980</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.
Next particle to be examined by the algorithm has the current minimum of new event times. At examining the chosen particle,
Line 39 ⟶ 36:
== 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>
== References ==
| |||