Algoritmul Lubachevsky- Stillinger ( LSA ) este o procedură de calcul care simulează procesul de compresie mecanică a unui set de particule solide .
Comprimarea mecanică este efectuată de obicei de peretele vasului în care sunt situate particulele, de exemplu, printr-un piston care presează particulele . LSA vă permite să modelați acest proces [1] .
În formularea originală, LSA nu a presupus o limită rigidă - particulele simulate s-au extins în timp ce se aflau într-un volum virtual fix și finit cu condiții de limită periodice [2] [3] . Dimensiunile absolute ale particulelor au crescut, dar dimensiunile lor relative au rămas neschimbate. LSA poate simula, de asemenea, compresia externă cu expansiunea internă simultană a particulelor.
În starea rezultată, unele particule își pot păstra mobilitatea în limitele vecinilor și pereților vasului. Apariția unor astfel de particule a fost neașteptată pentru autorii algoritmului - Frank Stillinger a propus denumirea de „ratler” (zdrăngănitor) pentru o astfel de particule, deoarece ratlers vor „răuși” dacă scuturați o serie comprimată de particule solide.
Contracția externă și expansiunea internă a particulelor pot fi oprite în starea precomprimată atunci când densitatea de umplere a particulelor este scăzută și particulele sunt mobile. Funcționând în acest mod, LSA va simula fluxul de particule ca mediu granular . LSA poate modela, de asemenea, diferite mecanisme de coliziune a particulelor sau poate lua în considerare masa acestora.
Utilizarea LSA pentru particule sferice sau în containere cu dimensiuni „incomode” s-a dovedit a fi eficientă în reproducerea și demonstrarea tulburărilor microstructurale asociate cu defecte de cristal [4] sau frustrări geometrice [5] [6] . Inițial, LSA a fost destinat să rezolve problema împachetării mingii [7] . LSA poate gestiona seturi de zeci și sute de mii de bile pe computerele personale, cu toate acestea, abaterea de la forma sferică (sau rotundă pe plan), cum ar fi utilizarea elipsoizilor (elipse pe plan), încetinește semnificativ calculele [ 8] .
Pentru compresie, se utilizează modelarea cu evenimente discrete a unui mediu granular, unde evenimentele sunt ciocnirile particulelor între ele și cu pereții solizi, dacă există. Calculele se opresc atunci când deplasările între ciocnirile tuturor particulelor, cu excepția rășinilor, devin mai mici decât un prag mic specificat explicit sau implicit, care poate fi determinat, de exemplu, prin erori de rotunjire.
LSA este eficient din punct de vedere computațional, în sensul că progresul său este determinat de evenimente (coliziuni) mai degrabă decât de timpul scurs între ele. În acest sens, caracteristicile intermediare ale particulelor în perioada dintre coliziunile solare, de regulă, nu sunt calculate. În comparație cu alți algoritmi cu un model de calcul similar, precum algoritmul lui D. Rapaport [9] , LSA se remarcă prin simplitatea sa în structurarea și procesarea datelor.
Pentru orice particulă și în orice etapă de calcul, LSA menține o înregistrare a doar două evenimente: un eveniment vechi care a fost deja procesat și unul nou care este programat pentru procesare. O înregistrare a evenimentului constă în marcajul de timp al evenimentului, starea particulei imediat după eveniment (inclusiv poziția și viteza particulei) și o indicație a „partenerului” particulei în acest eveniment (o altă particule sau peretele vasului). ), dacă este cazul. Etichetele maxime dintre evenimentele gestionate nu trebuie să depășească etichetele minime ale evenimentelor netratate.
Următoarea particulă care urmează să fie procesată este particula cu cea mai mică amprentă temporală dintre evenimentele neprocesate. Evenimentul asociat cu această particulă este declarat procesat și, în același timp, următorul eveniment este programat pentru acesta cu un nou marcaj de timp, o nouă stare și un nou partener, dacă există. În același timp, evenimentele brute așteptate pentru unii cei mai apropiați vecini ai acestei particule se pot schimba.
Pe măsură ce calculele progresează, ratele de coliziune ale particulelor tind să crească. Cu toate acestea, sistemul se apropie cu succes de starea comprimată dacă frecvențele de coliziune ale diferitelor particule, care nu sunt zgomote, se dovedesc a fi comparabile. Rattlers, la rândul lor, mențin o rată de coliziune constant scăzută, ceea ce le permite să fie detectate.
În același timp, este posibil ca frecvența de coliziune a unui număr mic de particule, sau chiar a unei particule, să depășească semnificativ frecvența de coliziune a restului particulelor, ceea ce, la rândul său, poate încetini semnificativ algoritmul. O astfel de stare în simularea mediilor granulare este de obicei numită „colaps inelastic” deoarece cauza ei tipică este coeficientul scăzut de restituire al particulelor simulate [10] . Această situație nu este unică pentru LSA și au fost dezvoltate o serie de metode pentru a face față acesteia [11] .
LSA a apărut ca un produs secundar al unei încercări de a stabili o măsură adecvată a accelerării simulării paralele . Inițial, s-a propus utilizarea algoritmului paralel Time Warp [12] - accelerația a fost definită ca raportul dintre timpul de execuție pe sistemele multiprocesor și uniprocesor. Boris Dmitrievich Lyubachevsky a remarcat că o astfel de estimare poate fi supraestimată, deoarece executarea unei sarcini pe un procesor folosind un program paralel poate să nu fie optimă pentru rezolvarea sarcinii. LSA a fost creat ca o încercare de a găsi o metodă de simulare uniprocesor mai rapidă și, prin urmare, de a îmbunătăți calitatea estimării accelerației paralele. Ulterior, a fost propus și un algoritm de simulare paralel, care, atunci când este executat pe un sistem cu un singur procesor, este identic cu LSA [13] .