Lubachevsky- Stillinger-algoritmi ( LSA ) on laskennallinen menettely , joka simuloi kiinteiden hiukkasten joukon mekaanista puristusprosessia .
Mekaaninen puristus suoritetaan yleensä astian seinämällä, jossa hiukkaset sijaitsevat, esimerkiksi männän avulla, joka puristaa hiukkasia . LSA mahdollistaa tämän prosessin mallintamisen [1] .
Alkuperäisessä formulaatiossa LSA ei olettanut jäykkää rajaa - simuloidut hiukkaset laajenivat ollessaan kiinteässä ja rajallisessa virtuaalisessa tilavuudessa jaksollisin rajaehdoin [2] [3] . Absoluuttiset hiukkaskoot kasvoivat, mutta niiden suhteelliset koot pysyivät ennallaan. LSA voi myös simuloida ulkoista puristusta ja samanaikaisesti hiukkasten sisäistä laajenemista.
Tuloksena olevassa tilassa jotkin hiukkaset voivat säilyttää liikkuvuuden naapuriensa ja suonen seinämiensä rajoissa. Tällaisten hiukkasten ilmestyminen oli odottamaton algoritmin tekijöille - Frank Stillinger ehdotti tällaiselle hiukkaselle nimeä "ratler" (rattle), koska helistimet "jyristyvät", jos ravistat puristettua kiinteiden hiukkasten joukkoa.
Partikkelien ulkoinen supistuminen ja sisäinen laajeneminen voidaan pysäyttää esipuristetussa tilassa, kun hiukkasten täyttötiheys on pieni ja hiukkaset liikkuvat. Tässä tilassa LSA simuloi hiukkasten virtausta rakeisena väliaineena . LSA voi myös mallintaa erilaisia hiukkasten törmäysmekanismeja tai ottaa huomioon niiden massan.
LSA:n käyttö pallomaisissa hiukkasissa tai "epämiellyttävän" kokoisissa säiliöissä on osoittautunut tehokkaaksi kidevirheisiin [4] tai geometriseen turhautumiseen [5] [6] liittyvien mikrorakennehäiriöiden toistamisessa ja osoittamisessa . Aluksi LSA:n tarkoituksena oli ratkaista pallopakkausongelma [7] . LSA pystyy käsittelemään kymmenien ja satojen tuhansien pallojen sarjoja henkilökohtaisissa tietokoneissa, mutta poikkeama pallomaisesta muodosta (tai pyöreästä tasossa), kuten ellipsoidien (tasossa ellipsien) käyttö hidastaa laskelmia merkittävästi [ 8] .
Puristamiseen käytetään rakeisen väliaineen diskreettitapahtumamallinnusta , jossa tapahtumat ovat hiukkasten törmäykset keskenään ja mahdollisten kiinteiden seinien kanssa. Laskelmat pysähtyvät, kun kaikkien hiukkasten törmäysten väliset siirtymät, paitsi helistimet, jäävät pienemmäksi kuin eksplisiittisesti tai implisiittisesti määritelty pieni kynnys, joka voidaan määrittää esimerkiksi pyöristysvirheillä.
LSA on laskennallisesti tehokas siinä mielessä, että sen etenemisen määräävät tapahtumat (törmäykset) pikemminkin kuin niiden välillä kulunut aika. Tässä suhteessa hiukkasten väliominaisuuksia aurinkotörmäysten välisenä aikana ei yleensä lasketa. Verrattuna muihin algoritmeihin, joilla on samanlainen laskentamalli, kuten D. Rapaportin algoritmi [9] , LSA erottuu yksinkertaisuudestaan tiedon strukturoinnissa ja käsittelyssä.
Kaikille hiukkasille ja missä tahansa laskentavaiheessa LSA ylläpitää kirjaa vain kahdesta tapahtumasta: vanhasta tapahtumasta, joka on jo käsitelty, ja uudesta tapahtumasta, joka on ajoitettu käsiteltäväksi. Tapahtumatietue koostuu tapahtuman aikaleimasta , hiukkasen tilasta välittömästi tapahtuman jälkeen (mukaan lukien hiukkasen sijainti ja nopeus) sekä osoituksen hiukkasen "kumppanista" tässä tapahtumassa (toinen hiukkanen tai suonen seinämä). ), jos mitään. Käsiteltyjen tapahtumien enimmäistunnisteet eivät saa ylittää käsittelemättömien tapahtumien vähimmäistunnisteita.
Seuraavaksi käsiteltävä partikkeli on pienin aikaleima käsittelemättömistä tapahtumista. Tähän hiukkaseen liittyvä tapahtuma julistetaan käsitellyksi, ja samalla sille ajoitetaan seuraava tapahtuma uudella aikaleimalla, uudella tilalla ja uudella kumppanilla, jos sellainen on. Samaan aikaan tämän hiukkasen joidenkin lähimpien naapureiden odotetut raakatapahtumat voivat muuttua.
Laskelmien edetessä hiukkasten törmäysnopeudet kasvavat. Järjestelmä kuitenkin lähestyy onnistuneesti kompressoitua tilaa, jos eri hiukkasten, jotka eivät ole räjähtäviä, törmäystaajuudet osoittautuvat vertailukelpoisiksi. Helistit puolestaan ylläpitävät jatkuvasti matalaa törmäysprosenttia, mikä mahdollistaa niiden havaitsemisen.
Samalla on mahdollista, että pienen määrän tai jopa yhden hiukkasen törmäystaajuudet ylittävät merkittävästi muiden hiukkasten törmäystaajuuden, mikä puolestaan voi hidastaa algoritmia merkittävästi. Tällaista tilaa rakeisen väliaineen simuloinnissa kutsutaan yleensä "elastiseksi romahdukseksi" , koska sen tyypillinen syy on simuloitujen hiukkasten alhainen palautuskerroin [10] . Tämä tilanne ei ole ainutlaatuinen LSA:lle, ja sen ratkaisemiseksi on kehitetty useita menetelmiä [11] .
LSA syntyi sivutuotteena yritykseltä saada riittävä mitta rinnakkaisen simulaation nopeuden Aluksi ehdotettiin rinnakkaisen Time Warp -algoritmin käyttöä [12] - kiihtyvyys määriteltiin suoritusajan suhteeksi moniprosessori- ja yksiprosessorijärjestelmissä. Boris Dmitrievich Lyubachevsky totesi, että tällainen arvio voidaan yliarvioida, koska tehtävän suorittaminen yhdellä prosessorilla rinnakkaisohjelmalla ei välttämättä ole optimaalinen tehtävän ratkaisemiseksi. LSA luotiin yritykseksi löytää nopeampi yksiprosessorisimulaatiomenetelmä ja siten parantaa rinnakkaisnopeusestimoinnin laatua. Myöhemmin ehdotettiin myös rinnakkaissimulaatioalgoritmia, joka suoritettuna yhdellä prosessorijärjestelmällä on identtinen LSA:n kanssa [13] .