Swendsen–Wang-algoritm

Swendsen –Wang-algoritmen är den första icke-lokala eller klusteralgoritmen för Monte Carlo-simulering för stora system nära kritikalitet . Det har introducerats av Robert Swendsen och Jian-Sheng Wang 1987 på Carnegie Mellon .

Den ursprungliga algoritmen designades för Ising- och Potts-modellerna, och den generaliserades senare till andra system också, såsom XY-modellen av Wolff-algoritmen och partiklar av vätskor. Nyckelingrediensen var den slumpmässiga klustermodellen , en representation av Ising- eller Potts -modellen genom perkolationsmodeller av förbindande bindningar, på grund av Fortuin och Kasteleyn. Det har generaliserats av Barbu och Zhu till godtyckliga samplingssannolikheter genom att se det som en Metropolis–Hastings-algoritm och beräkna acceptanssannolikheten för det föreslagna Monte Carlo-draget.

Motivering

Problemet med den kritiska avmattningen som påverkar lokala processer är av grundläggande betydelse i studiet av andra ordningens fasövergångar (som ferromagnetisk övergång i Ising-modellen ), eftersom en ökning av systemets storlek för att minska effekterna av ändlig storlek har nackdelen med att kräva ett mycket större antal rörelser för att nå termisk jämvikt. Faktum är att korrelationstiden $\tau$ vanligtvis ökar som $L^{z}$ med $z\simeq 2$ eller högre; eftersom simuleringstiden för att vara korrekt måste vara ${\displaystyle t\gg \tau } ,$ är detta en stor begränsning i storleken på systemen som kan studeras genom lokala algoritmer. SW-algoritmen var den första som producerade ovanligt små värden för de dynamiskt kritiska exponenterna: $z=0,35$ för 2D Ising-modellen ( $z=2,125$ för standardsimuleringar); $z=0,75$ för 3D Ising-modellen, i motsats till $z=2,0$ för standardsimuleringar.

Beskrivning

Huvudartikel: Slumpmässig klustermodell

Algoritmen är icke-lokal i den meningen att ett enda svep uppdaterar en samling spinnvariabler baserade på Fortuin–Kasteleyn-representationen . Uppdateringen görs på ett "kluster" av snurrvariabler kopplade av öppna bindningsvariabler som genereras genom en perkolationsprocess , baserat på interaktionstillstånden för snurren.

Tänk på en typisk ferromagnetisk Ising-modell med endast interaktion med närmaste granne.

• Med utgångspunkt från en given konfiguration av snurr, associerar vi till varje par av närmaste grannar på webbplatser $n,m$ en slumpmässig variabel $b_{n,m}\ i \lbrace 0,1\rbrace$ vilket tolkas på följande sätt: om $b_{n,m}=0$ så finns det ingen länk mellan webbplatserna $n$ och $m$ (bindningen är stängd ); om $b_{n,m}=1$ så finns det en länk som förbinder spinnen $\sigma _{n}{\text{ och }}\sigma _{m}$ (obligationen är öppen ). Dessa värden tilldelas enligt följande (villkorliga) sannolikhetsfördelning:

 $P\left[b_{n,m}=0|\sigma _{n}\neq \sigma _{m}\right]=1$ ; $P\left[b_{n,m}=1|\sigma _{n}\neq \sigma _{m}\right]=0$ ; $P\left[b_{n,m}=0|\sigma _{n}=\sigma _{m}\right]=e^{ -2\beta J_{nm}}$ ; $P\left[b_{n,m}=1|\sigma _{n}=\sigma _{m}\right]=1 -e^{-2\beta J_{nm}}$ ; 

där $J_{nm}>0$ är den ferromagnetiska kopplingsstyrkan.

Denna sannolikhetsfördelning har härletts på följande sätt: Hamiltonian för Ising-modellen är

$H[\sigma ]=\summa \limits _{<i,j>}-J_{i,j}\sigma _{i}\sigma _{j}$ ,

och partitionsfunktionen är

$Z=\sum \limits _{\lbrace \sigma \rbrace }e^{-\beta H[\sigma ]}$ .

Betrakta interaktionen mellan ett par utvalda platser $n$ och $m$ och eliminera det från den totala Hamiltonian, definiera $H_{nm}[\sigma ]=\sum \limits _{<i,j>\neq <n,m>}-J_{i,j}\sigma _{i}\sigma _{j} .$

Definiera även de begränsade summorna:

$Z_{n,m}^{samma}=\summa \limits _{\lbrace \sigma \rbrace }e^{-\beta H_{nm}[\sigma ]}\delta _{\sigma _{n},\sigma _{m}}$ ;

$Z_{n,m}^{diff}=\sum \limits _{\lbrace \sigma \rbrace }e^{-\beta H_{nm}[\sigma ]}\left(1-\delta _ {\sigma _{n},\sigma _{m}}\right).$

$Z=e^{\beta J_{nm}}Z_{n,m}^{same}+e^{-\beta J_{nm}}Z_{n,m}^{diff}.$

Introducera mängden

$Z_{nm}^{ind}=Z_{n,m}^{samma}+Z_{n ,m}^{diff}$ ;

partitionsfunktionen kan skrivas om som

$Z=\left(e^{\beta J_{nm}}-e^{-\beta J_{nm}}\right)Z_{n,m}^{samma}+e^{-\beta J_{nm}}Z_{n,m}^{ind}.$

${\displaystyle P_{<n,m>\;link}=1-e^{-2\beta J_{nm}}.} Processen kan$ begränsning i den andra termen, kan viktningsfaktorerna (korrekt normaliserade) tolkas som sannolikheter för att bilda/inte bilda en länk mellan platserna: P enkelt anpassas till antiferromagnetiska spinnsystem, eftersom det är tillräckligt för att eliminera $Z_{n,m}^{samma}$ till förmån för $Z_{n,m}^{diff}$ (som föreslås av byte av tecken i interaktionskonstanten).

• Efter att ha tilldelats bindningsvariablerna identifierar vi samma spinnkluster som bildas av anslutna platser och gör en inversion av alla variabler i klustret med sannolikhet 1/2. Vid följande tidssteg har vi en ny start-Ising-konfiguration, som kommer att producera en ny klustring och en ny kollektiv spin-flip.

Rätthet

Det kan visas att denna algoritm leder till jämviktskonfigurationer. För att visa detta tolkar vi algoritmen som en Markov-kedja och visar att kedjan är både ergodisk (när den används tillsammans med andra algoritmer) och uppfyller detaljerad balans , så att Boltzmann-balansfördelningen är lika med den stationära fördelningen av kedjan.

Ergodicitet innebär att det är möjligt att gå från vilket initialt tillstånd som helst till vilket slutligt tillstånd som helst med ett begränsat antal uppdateringar. Det har visat sig att SW-algoritmen inte är ergod i allmänhet (i den termodynamiska gränsen). Så i praktiken används SW-algoritmen vanligtvis i kombination med enstaka spin-flip-algoritmer som Metropolis-Hastings-algoritmen för att uppnå ergodicitet.

SW-algoritmen uppfyller dock detaljerad balans. För att visa detta, noterar vi att varje övergång mellan två Ising-spintillstånd måste passera genom någon bindningskonfiguration i perkolationsrepresentationen. Låt oss fixa en viss bindningskonfiguration: det som spelar roll vid jämförelse av sannolikheterna relaterade till den är antalet faktorer $q=e^{-2\beta J}$ för varje saknad bindning mellan angränsande snurr med samma värde; sannolikheten att gå till en viss Ising-konfiguration som är kompatibel med en given bindningskonfiguration är enhetlig (säg ${\displaystyle p} )$ . Så förhållandet mellan övergångssannolikheterna för att gå från ett tillstånd till ett annat är

${\frac {P_{\lbrace \sigma \rbrace \rightarrow \lbrace \sigma '\rbrace }}{P_{\lbrace \sigma '\rbrace \rightarrow \lbrace \sigma \rbrace }}}={\frac {Pr\left(\lbrace \sigma '\rbrace |BC\right)Pr\left(BC| \lbrace \sigma \rbrace \right)}{Pr\left(\lbrace \sigma \rbrace |BC\right)Pr\left(BC|\lbrace \sigma '\rbrace \right)}}={\frac {p \cdot \exp \left[-2\beta \sum \limits _{<l,m>}\delta _{\sigma _{l},\sigma _{m}}J_{lm}\right]}{ p\cdot \exp \left[-2\beta \sum \limits _{<l,m>}\delta _{\sigma '_{l},\sigma '_{m}}J_{lm}\right ]}}=e^{-\beta \Delta E}$

eftersom $\Delta E=-\sum \limits _{<l,m>}J_{lm}\left(\sigma '_{l}\sigma '_{m}- \sigma _{l}\sigma _{m}\right)=-\summa \limits _{<l,m>}J_{lm}\left[\delta _{\sigma '_{l},\sigma '_{m}}-\left(1-\delta _{\sigma '_{l},\sigma '_{m}}\right)-\delta _{\sigma _{l},\sigma _ {m}}+\left(1-\delta _{\sigma _{l},\sigma _{m}}\right)\right]=-2\summa \limits _{<l,m>}J_ {lm}\left(\delta _{\sigma '_{l},\sigma '_{m}}-\delta _{\sigma _{l},\sigma _{m}}\right)$ .

Detta är giltigt för varje bindningskonfiguration som systemet kan passera genom under sin utveckling, så en detaljerad balans är uppfylld för den totala övergångssannolikheten. Detta bevisar att algoritmen är korrekt.

Effektivitet

Även om det inte är analytiskt tydligt från originaldokumentet, är anledningen till att alla värden för z som erhålls med SW-algoritmen mycket lägre än den exakta nedre gränsen för single-spin-flip-algoritmer ( z ≥ γ / ν { $\ gamma /\nu }$ ) är att korrelationslängddivergensen är strikt relaterad till bildandet av perkolationskluster, som vänds ihop. På så sätt reduceras avslappningstiden avsevärt. Ett annat sätt att se detta är genom överensstämmelsen mellan spinstatistiken och klusterstatistiken i Edwards-Sokal-representationen .

Generaliseringar

Algoritmen är inte effektiv för att simulera frustrerade system , eftersom korrelationslängden för klustren är större än korrelationslängden för spinnmodellen i närvaro av frustrerade interaktioner. För närvarande finns det två huvudsakliga tillvägagångssätt för att ta itu med detta problem, så att effektiviteten hos klusteralgoritmer utvidgas till frustrerade system.

Det första tillvägagångssättet är att utöka reglerna för bindningsbildning till fler icke-lokala celler, och det andra tillvägagångssättet är att generera kluster baserat på mer relevanta ordningsparametrar. I det första fallet har vi KBD-algoritmen för den helt frustrerade Ising-modellen , där beslutet om att öppna bindningar tas på varje plakett, arrangerad i ett rutmönster på det kvadratiska gittret. I det andra fallet har vi replika-klusterflyttning för lågdimensionella spinglasögon , där klustren genereras baserat på spinnöverlappningar, vilket tros vara den relevanta ordningsparametern.

Se även

• Slumpmässig klustermodell
• Monte Carlo metoden
• Wolff algoritm
• http://www.hpjava.org/theses/shko/thesis_paper/node69.html
• http://www-fcs.acs.i.kyoto-u.ac.jp/~harada/monte-en.html

•    Swendsen, Robert H.; Wang, Jian-Sheng (1987-01-12). "Icke-universell kritisk dynamik i Monte Carlo-simuleringar". Fysiska granskningsbrev . American Physical Society (APS). 58 (2): 86–88. Bibcode : 1987PhRvL..58...86S . doi : 10.1103/physrevlett.58.86 . ISSN 0031-9007 . PMID 10034599 .
• Kasteleyn PW och Fortuin (1969) J. Phys. Soc. Jpn. Suppl. 26s:11
•   Fortuin, CM; Kasteleyn, PW (1972). "På den slumpmässiga klustermodellen". Physica . Elsevier BV. 57 (4): 536–564. Bibcode : 1972Phy....57..536F . doi : 10.1016/0031-8914(72)90045-6 . ISSN 0031-8914 .
•   Wang, Jian-Sheng; Swendsen, Robert H. (1990). "Kluster Monte Carlo-algoritmer". Physica A: Statistisk mekanik och dess tillämpningar . Elsevier BV. 167 (3): 565–579. Bibcode : 1990PhyA..167..565W . doi : 10.1016/0378-4371(90)90275-w . ISSN 0378-4371 .
•     Barbu, A. (2005). "Generalisera Swendsen-Wang till provtagning av godtyckliga posteriora sannolikheter". IEEE-transaktioner på mönsteranalys och maskinintelligens . Institutet för el- och elektronikingenjörer (IEEE). 27 (8): 1239–1253. doi : 10.1109/tpami.2005.161 . ISSN 0162-8828 . PMID 16119263 . S2CID 410716 .