Lubachevsky–Stillinger algorithm

Lubachevsky-Stillinger (compression) algorithm (LS algorithm, LSA, or LS protocol) is a numerical procedure suggested by F. H. Stillinger and Boris D. Lubachevsky that simulates or imitates a physical process of compressing an assembly of hard particles.

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 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.

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.

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.

The real calculations are stopped when inter-collision runs of the non-rattler particles become smaller than an explicitly or implicitly specified small threshold.

This means almost no calculation is wasted on computing or maintaining the positions and velocities of the particles between the collisions.

Still the LSA successfully approaches the jamming state as long as those rates remain comparable among all the particles, except for the rattlers.

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.