Lubachevsky -Stillinger-algoritmen ( LSA ) är en beräkningsprocedur som simulerar processen för mekanisk komprimering av en uppsättning fasta partiklar .
Mekanisk komprimering utförs vanligtvis av kärlets vägg där partiklarna finns, till exempel genom att en kolv trycker på partiklarna . LSA låter dig modellera denna process [1] .
I den ursprungliga formuleringen antog LSA inte en stel gräns - de simulerade partiklarna expanderade samtidigt som de var i en fixerad och ändlig virtuell volym med periodiska randvillkor [2] [3] . De absoluta partikelstorlekarna ökade, men deras relativa storlekar förblev oförändrade. LSA kan också simulera extern kompression med samtidig intern expansion av partiklar.
I det resulterande tillståndet kan vissa partiklar behålla sin rörlighet inom gränserna för sina grannar och kärlväggar. Uppkomsten av sådana partiklar var oväntat för författarna till algoritmen - Frank Stillinger föreslog namnet "ratler" (skrammel) för en sådan partikel, eftersom ratlers kommer att "rumla" om du skakar en komprimerad samling fasta partiklar.
Den yttre sammandragningen och inre expansionen av partiklarna kan stoppas i det förkomprimerade tillståndet när partikelfyllningsdensiteten är låg och partiklarna är rörliga. I detta läge simulerar LSA flödet av partiklar som ett granulärt medium . LSA kan också modellera olika partikelkollisionsmekanismer eller ta hänsyn till deras massa.
Användningen av LSA för sfäriska partiklar eller i behållare med "obekväma" storlekar har visat sig vara effektiv för att reproducera och demonstrera mikrostrukturella störningar associerade med kristalldefekter [4] eller geometrisk frustration [5] [6] . Inledningsvis var LSA tänkt att lösa problemet med bollpackning [7] . LSA kan hantera uppsättningar av tiotals och hundratusentals bollar på persondatorer, men avvikelser från den sfäriska formen (eller runda på planet), såsom användningen av ellipsoider (ellipser på planet), saktar avsevärt ner beräkningarna [ 8] .
För komprimering används diskret-händelsemodellering av ett granulärt medium, där händelserna är kollisioner av partiklar med varandra och med solida väggar, om några. Beräkningar stoppar när förskjutningarna mellan kollisioner av alla partiklar, utom ratlers, blir mindre än en explicit eller implicit specificerad liten tröskel, som kan bestämmas till exempel genom avrundningsfel.
LSA är beräkningseffektiv, i den meningen att dess framsteg bestäms av händelser (kollisioner) snarare än av hur lång tid som förflutit mellan dem. I detta avseende beräknas som regel inte de mellanliggande egenskaperna hos partiklar i perioden mellan solkollisioner. Jämfört med andra algoritmer med en liknande beräkningsmodell, såsom D. Rapaports algoritm [9] utmärker sig LSA för sin enkelhet i datastrukturering och bearbetning.
För varje partikel och i vilket skede av beräkning som helst, upprätthåller LSA endast två händelser: en gammal händelse som redan har bearbetats och en ny som är schemalagd för bearbetning. En händelsepost består av tidsstämpeln för händelsen, partikelns tillstånd omedelbart efter händelsen (inklusive partikelns position och hastighet), och en indikation på partikelns "partner" i denna händelse (en annan partikel eller kärlvägg) ), om någon. Det maximala antalet etiketter bland hanterade händelser får inte överstiga minimietiketterna för obehandlade händelser.
Nästa partikel som ska bearbetas är den partikel med den minsta tidsstämpeln bland de obearbetade händelserna. Händelsen som är associerad med denna partikel förklaras bearbetad, och samtidigt schemaläggs nästa händelse för den med en ny tidsstämpel, ett nytt tillstånd och en ny partner, om någon. Samtidigt kan de förväntade råhändelserna för vissa närmaste grannar till denna partikel förändras.
När beräkningarna fortskrider tenderar partikelkollisionshastigheterna att öka. Systemet närmar sig dock framgångsrikt det komprimerade tillståndet om kollisionsfrekvenserna för olika partiklar, som inte är ratlers, visar sig vara jämförbara. Skramlare upprätthåller i sin tur en konsekvent låg kollisionshastighet, vilket gör att de kan upptäckas.
Samtidigt är det möjligt att kollisionsfrekvenserna för ett litet antal partiklar, eller till och med en partikel, kommer att avsevärt överstiga kollisionsfrekvensen för resten av partiklarna, vilket i sin tur kan avsevärt bromsa algoritmen. Ett sådant tillstånd i simuleringen av granulära medier kallas vanligtvis "oelastisk kollaps" eftersom dess typiska orsak är den låga restitutionskoefficienten för de simulerade partiklarna [10] . Denna situation är inte unik för LSA, och ett antal metoder har utvecklats för att hantera den [11] .
LSA kom till som en biprodukt av ett försök att fastställa ett adekvat mått på hastigheten parallell simulering. Inledningsvis föreslogs det att använda den parallella Time Warp- algoritmen [12] - acceleration definierades som förhållandet mellan exekveringstiden på system med flera processorer och enprocessorer. Boris Dmitrievich Lyubachevsky noterade att en sådan uppskattning kan överskattas, eftersom exekveringen av en uppgift på en processor med ett parallellt program kanske inte är optimal för att lösa uppgiften. LSA skapades som ett försök att hitta en snabbare enprocessorsimuleringsmetod och därigenom förbättra kvaliteten på den parallella hastighetsuppskattningen. Därefter föreslogs också en parallell simuleringsalgoritm, som, när den exekveras på ett enda processorsystem, är identisk med LSA [13] .