Lubačevského- Stillingerův algoritmus ( LSA ) je výpočetní procedura , která simuluje proces mechanické komprese sady pevných částic .
Mechanické stlačení se obvykle provádí stěnou nádoby, kde jsou částice umístěny, například pístem , který na částice tlačí . LSA umožňuje modelovat tento proces [1] .
V původní formulaci LSA nepředpokládala rigidní hranici - simulované částice expandovaly, zatímco byly v pevném a konečném virtuálním objemu s periodickými okrajovými podmínkami [2] [3] . Absolutní velikosti částic se zvýšily, ale jejich relativní velikosti zůstaly nezměněny. LSA může také simulovat vnější kompresi se současnou vnitřní expanzí částic.
Ve výsledném stavu si některé částice mohou zachovat pohyblivost v mezích svých sousedů a stěn cév. Vzhled takových částic byl pro autory algoritmu neočekávaný - Frank Stillinger navrhl pro takovou částici název „ratler“ (chrastítko), protože ratlery budou „rachotit“, pokud zatřesete stlačeným polem pevných částic.
Vnější kontrakci a vnitřní expanzi částic lze zastavit v předem stlačeném stavu, když je hustota náplně částic nízká a částice jsou pohyblivé. V tomto režimu bude LSA simulovat tok částic jako zrnité médium . LSA může také modelovat různé mechanismy srážek částic nebo brát v úvahu jejich hmotnost.
Použití LSA pro sférické částice nebo v nádobách s „nepohodlnými“ velikostmi se ukázalo jako účinné při reprodukci a demonstraci mikrostrukturálních poruch spojených s krystalovými defekty [4] nebo geometrickou frustrací [5] [6] . Zpočátku bylo zamýšleno LSA vyřešit problém balení kuliček [7] . LSA zvládne na osobních počítačích sady desítek a stovek tisíc kuliček, nicméně odchylka od kulového tvaru (nebo kulatého na rovině), např. použití elipsoidů (elips v rovině), výrazně zpomaluje výpočty [ 8] .
Pro kompresi se používá modelování diskrétních událostí zrnitého prostředí, kde událostmi jsou srážky částic mezi sebou as pevnými stěnami, pokud nějaké jsou. Výpočty se zastaví, když posuny mezi srážkami všech částic, kromě ratlerů, budou menší než explicitně nebo implicitně specifikovaný malý práh, který lze určit například chybami zaokrouhlování.
LSA je výpočetně efektivní v tom smyslu, že jeho průběh je určován událostmi (kolizemi) spíše než množstvím času, který mezi nimi uplynul. V tomto ohledu se mezilehlé charakteristiky částic v období mezi slunečními srážkami zpravidla nepočítají. Ve srovnání s jinými algoritmy s podobným výpočtovým modelem, jako je algoritmus D. Rapaporta [9] , vyniká LSA svou jednoduchostí při strukturování a zpracování dat.
Pro jakoukoli částici a v jakékoli fázi výpočtu udržuje LSA záznam pouze dvou událostí: staré události, která již byla zpracována, a nové události, která je naplánována ke zpracování. Záznam události se skládá z časového razítka události, stavu částice bezprostředně po události (včetně polohy a rychlosti částice) a označení „partnera“ částice v této události (jiná částice nebo stěna nádoby ), jestli nějaký. Maximální počet štítků mezi zpracovanými událostmi nesmí překročit minimální počet štítků nezpracovaných událostí.
Další částice, která má být zpracována, je částice s nejmenším časovým razítkem mezi nezpracovanými událostmi. Událost spojená s touto částicí je prohlášena za zpracovanou a zároveň je pro ni naplánována další událost s novým časovým razítkem, novým stavem a novým partnerem, pokud existuje. Současně se mohou změnit očekávané hrubé události pro některé nejbližší sousedy této částice.
Jak výpočty postupují, mají četnost srážek částic tendenci se zvyšovat. Systém se však úspěšně přiblíží ke stlačenému stavu, pokud se srážkové frekvence různých částic, které nejsou ratlery, ukážou jako srovnatelné. Rattlers si zase udržují trvale nízkou míru kolizí, což umožňuje jejich detekci.
Zároveň je možné, že srážkové frekvence malého počtu částic, nebo dokonce jedné částice, výrazně překročí srážkovou frekvenci zbytku částic, což zase může výrazně zpomalit algoritmus. Takový stav při simulaci zrnitých médií se obvykle nazývá „neelastický kolaps“ , protože jeho typickou příčinou je nízký koeficient restituce simulovaných částic [10] . Tato situace není pro LSA jedinečná a pro její řešení byla vyvinuta řada metod [11] .
LSA vzniklo jako vedlejší produkt pokusu stanovit adekvátní míru zrychlení paralelní simulace. Původně bylo navrženo použít paralelní algoritmus Time Warp [12] - zrychlení bylo definováno jako poměr doby provádění na víceprocesorových a jednoprocesorových systémech. Boris Dmitrievich Lyubachevsky poznamenal, že takový odhad může být nadhodnocen, protože provedení úlohy na jednom procesoru pomocí paralelního programu nemusí být pro řešení úlohy optimální. LSA byl vytvořen jako pokus najít rychlejší jednoprocesorovou simulační metodu a tím zlepšit kvalitu odhadu paralelního zrychlení. Následně byl také navržen paralelní simulační algoritmus, který je při provádění na systému s jedním procesorem identický s LSA [13] .