A Lubacsevszkij- Stillinger algoritmus ( LSA ) egy számítási eljárás , amely szilárd részecskék halmazának mechanikai tömörítésének folyamatát szimulálja .
A mechanikai összenyomást általában az edény fala végzi, ahol a részecskék találhatók, például egy dugattyú , amely rányomja a részecskéket . Az LSA lehetővé teszi ennek a folyamatnak a modellezését [1] .
Az eredeti megfogalmazásban az LSA nem feltételezett merev határt – a szimulált részecskék kitágultak, miközben egy rögzített és véges virtuális térfogatban voltak periodikus peremfeltételekkel [2] [3] . Az abszolút részecskeméretek növekedtek, de relatív méretük változatlan maradt. Az LSA külső tömörítést is képes szimulálni a részecskék egyidejű belső tágulásával.
Az így létrejövő állapotban egyes részecskék megtarthatják mobilitásukat szomszédjaik és az érfalakon belül. Az ilyen részecskék megjelenése váratlan volt az algoritmus szerzői számára - Frank Stillinger a "ratler" (csörgő) nevet javasolta egy ilyen részecskének, mivel a csörgők "dübörögnek", ha szilárd részecskék tömörített tömbjét megrázzák.
A részecskék külső összehúzódása és belső tágulása elősűrített állapotban megállítható, ha a szemcsetöltési sűrűség alacsony és a részecskék mozgékonyak. Ebben az üzemmódban az LSA szemcsés közegként szimulálja a részecskék áramlását . Az LSA különböző részecskeütközési mechanizmusokat is képes modellezni, vagy figyelembe venni tömegüket.
Az LSA alkalmazása gömb alakú részecskékhez vagy „kényelmetlen” méretű tartályokban hatékonynak bizonyult a kristályhibákkal [4] vagy geometriai frusztrációval [5] [6] kapcsolatos mikroszerkezeti zavarok reprodukálására és kimutatására . Kezdetben az LSA-t a labdacsomagolási probléma megoldására szánták [7] . Az LSA személyi számítógépeken több tíz- és százezres golyós halmazokat is képes kezelni, azonban a gömb alakú (vagy a síkon kerek) eltérések, mint például az ellipszoidok (síkon ellipszisek) alkalmazása jelentősen lelassítja a számításokat [ 8] .
A tömörítéshez egy szemcsés közeg diszkrét eseménymodellezését használják, ahol az események részecskék ütközései egymással és szilárd falakkal, ha vannak ilyenek. A számítások leállnak, ha az összes részecske ütközése közötti elmozdulása, kivéve a csörgőket, kisebb lesz, mint egy kifejezetten vagy implicit módon meghatározott kis küszöbérték, amely például kerekítési hibákkal határozható meg.
Az LSA számítási szempontból hatékony, abban az értelemben, hogy előrehaladását az események (ütközések) határozzák meg, nem pedig a közöttük eltelt idő. Ebben a tekintetben a részecskék köztes jellemzőit a szoláris ütközések közötti időszakban általában nem számítják ki. Összehasonlítva más, hasonló számítási modellel rendelkező algoritmusokkal, mint például D. Rapaport algoritmusa [9] , az LSA az adatok strukturálása és feldolgozása egyszerűségével tűnik ki.
Bármely részecskére és a számítás bármely szakaszában az LSA csak két eseményt tart nyilván: egy régi eseményt, amelyet már feldolgoztak, és egy újat, amelyet feldolgozásra ütemeztek. Az eseményrekord az esemény időbélyegéből , a részecske közvetlenül az esemény utáni állapotából (beleértve a részecske helyzetét és sebességét), valamint a részecske „partnerének” az eseményben (egy másik részecske vagy érfal) jelzéséből áll. ), ha van ilyen. A kezelt események maximális címkéi nem haladhatják meg a kezeletlen események minimális címkéit.
A következő feldolgozandó részecske a legkisebb időbélyeggel rendelkező részecske a feldolgozatlan események közül. Az ehhez a részecskéhez társított eseményt feldolgozottnak nyilvánítja, és ezzel egyidejűleg a következő esemény ütemezése új időbélyeggel, új állapottal és új partnerrel, ha van ilyen. Ugyanakkor a részecske néhány legközelebbi szomszédjának várható nyers eseményei változhatnak.
A számítások előrehaladtával a részecskék ütközési aránya nő. A rendszer azonban sikeresen megközelíti a tömörített állapotot, ha a különböző részecskék ütközési gyakorisága, amelyek nem csörgők, összehasonlíthatónak bizonyulnak. A csörgők pedig állandóan alacsony ütközési arányt tartanak fenn, ami lehetővé teszi azok észlelését.
Ugyanakkor előfordulhat, hogy kis számú részecske, vagy akár egy részecske ütközési gyakorisága jelentősen meghaladja a többi részecske ütközési gyakoriságát, ami viszont jelentősen lelassíthatja az algoritmust. A szemcsés közeg szimulációjában egy ilyen állapotot általában "rugalmas összeomlásnak" neveznek, mivel tipikus oka a szimulált részecskék alacsony visszaállítási együtthatója [10] . Ez a helyzet nem egyedülálló az LSA-ra, és számos módszert fejlesztettek ki ennek kezelésére [11] .
Az LSA annak a kísérletnek a melléktermékeként jött létre, amely a párhuzamos szimuláció sebességének Kezdetben a párhuzamos Time Warp algoritmus [12] használatát javasolták – a gyorsulást a végrehajtási idő arányaként határozták meg többprocesszoros és egyprocesszoros rendszereken. Borisz Dmitrijevics Ljubacsevszkij megjegyezte, hogy egy ilyen becslés túlbecsülhető, mivel egy feladat végrehajtása egy processzoron párhuzamos programmal nem feltétlenül optimális a feladat megoldásához. Az LSA-t azért hozták létre, hogy egy gyorsabb egyprocesszoros szimulációs módszert találjanak, és ezáltal javítsák a párhuzamos gyorsulási becslés minőségét. Ezt követően egy párhuzamos szimulációs algoritmust is javasoltak, amely egyetlen processzoros rendszeren végrehajtva megegyezik az LSA-val [13] .