Content deleted Content added
m General fixes, replaced: = See Also = → = See also = |
some corrections: the SW algorithm is not ergodic in general. also added some discussions on the Edwards-Sokal represnetation |
||
Line 1:
The '''Swendsen–Wang algorithm''' is the first non-local or cluster [[algorithm]] for [[Monte Carlo simulation]] for large systems near [[Critical point (thermodynamics)|criticality]]. It has been introduced by [[Robert Swendsen]] and [[Jian-Sheng Wang]] in 1987 at [[Carnegie Mellon University|Carnegie Mellon]].
The original algorithm was designed for the [[Ising model|Ising]] and Potts models, and it was later generalized to other systems as well, such as the XY model by [[Wolff algorithm]] and particles of fluids. The key ingredient was the [[random cluster model]], a representation of the Ising or [[Potts model|Potts]] model through percolation models of connecting bonds, due to Fortuin and Kasteleyn. It has been generalized by Barbu and Zhu<ref>{{Cite
== Motivation ==
Line 8:
== Description ==
{{Main|Random cluster model}}
The algorithm is non-local in the sense that
Consider a typical ferromagnetic Ising model with only nearest-neighbor interaction.
* Starting from a given configuration of spins, we associate to each pair of nearest neighbours on sites <math>n,m</math> a random variable <math>b_{n,m}\in \lbrace 0,1\rbrace</math> which is interpreted in the following way: if <math>b_{n,m}=0</math> then there is no link between the sites <math>n</math> and <math>m</math> (the bond is '''closed'''); if <math>b_{n,m}=1</math>
<math>P\left[b_{n,m}=0|\sigma_n\neq\sigma_m\right]=1</math>;
Line 18:
<math>P\left[b_{n,m}=0|\sigma_n=\sigma_m\right]=e^{-2\beta J_{nm}}</math>;
<math>P\left[b_{n,m}=1|\sigma_n=\sigma_m\right]=1-e^{-2\beta J_{nm}}</math>;
where <math>J_{nm}>0</math> is the ferromagnetic
This probability distribution has been derived in the following way: the Hamiltonian of the Ising model is
Line 53:
== Correctness ==
It can be shown that this algorithm leads to equilibrium configurations.
Ergodicity means that it is possible to transit from any initial state to any final state with a finite number of updates. It has been shown that the SW algorithm is not ergodic in general (in the thermodynamic limit).<ref>{{Cite journal|last=Gore|first=Vivek K.|last2=Jerrum|first2=Mark R.|date=1999-10-01|title=The Swendsen–Wang Process Does Not Always Mix Rapidly|url=https://doi.org/10.1023/A:1004610900745|journal=Journal of Statistical Physics|language=en|volume=97|issue=1|pages=67–86|doi=10.1023/A:1004610900745|issn=1572-9613}}</ref> In practice, the SW algorithm is usually used in conjunction with single spin-flip algorithms such as the Metropolis-Hastings algorithm to achieve ergodicity.
Alternatively, we can show explicitly that detailed balance is satisfied. Every transition between two Ising configurations must pass through some bond configuration in the percolation representation. Let's fix a particular bond configuration: what matters in comparing the probabilities related to it is the number of factors <math>q=e^{-2\beta J}</math> for each missing bond between neighboring spins with the same value; the probability of going to a certain Ising configuration compatible with a given bond configuration is uniform (say <math>p</math>). So the ratio of the transition probabilities of going from one state to another is▼
▲
<math>\frac{P_{\lbrace\sigma\rbrace\rightarrow\lbrace\sigma'\rbrace}}{P_{\lbrace\sigma'\rbrace\rightarrow\lbrace\sigma\rbrace}}=\frac{Pr\left(\lbrace\sigma'\rbrace|B.C.\right)Pr\left(B.C.|\lbrace\sigma\rbrace\right)}{Pr\left(\lbrace\sigma\rbrace|B.C.\right)Pr\left(B.C.|\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]}
Line 62 ⟶ 64:
since <math>\Delta E=-\sum\limits_{<l,m>}J_{lm}\left(\sigma'_l \sigma'_m - \sigma_l \sigma_m\right)=-\sum\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\sum\limits_{<l,m>}J_{lm}\left(\delta_{\sigma'_l,\sigma'_m}-\delta_{\sigma_l,\sigma_m}\right)</math>.
This is valid for every bond configuration the system can pass through during its evolution, so detailed balance is satisfied for the total transition probability. This proves that the algorithm
== Efficiency ==
Although not analytically clear from the original paper, the reason why all the values of z obtained with the SW algorithm are much lower than the exact lower bound for single-spin-flip algorithms (<math>z\geq\gamma/\nu</math>) is that the correlation length divergence is strictly related to the formation of percolation clusters, which are flipped together. In this way the relaxation time is significantly reduced. Another way to view this is through the correspondence between the spin statistics and cluster statistics in the [[Random cluster model|Edwards-Sokal representation]].<ref>{{Cite journal|last=Edwards|first=Robert G.|last2=Sokal|first2=Alan D.|date=1988-09-15|title=Generalization of the Fortuin-Kasteleyn-Swendsen-Wang representation and Monte Carlo algorithm|url=https://link.aps.org/doi/10.1103/PhysRevD.38.2009|journal=Physical Review D|volume=38|issue=6|pages=2009–2012|doi=10.1103/PhysRevD.38.2009}}</ref>
The algorithm is not efficient in simulating [[Geometrical frustration|frustrated systems]], because the [[Percolation critical exponents|correlation length of the clusters]] is larger than the [[Correlation function (statistical mechanics)|correlation length of the spin model]] in the presence of frustrated interactions.<ref>{{Cite journal|last=Cataudella|first=V.|last2=Franzese|first2=G.|last3=Nicodemi|first3=M.|last4=Scala|first4=A.|last5=Coniglio|first5=A.|date=1994-03-07|title=Critical clusters and efficient dynamics for frustrated spin models|url=https://link.aps.org/doi/10.1103/PhysRevLett.72.1541|journal=Physical Review Letters|volume=72|issue=10|pages=1541–1544|doi=10.1103/PhysRevLett.72.1541}}</ref>
== See also ==
| |||