Swendsen–Wang algorithm: Difference between revisions

Revision as of 04:24, 18 April 2021

Revision as of 17:03, 18 April 2021

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 journal|last=Barbu|first=Adrian|last2=Zhu|first2=Song-Chun|date=August 2005-08|title=Generalizing Swendsen-Wang to sampling arbitrary posterior probabilities|url=https://pubmed.ncbi.nlm.nih.gov/16119263/|journal=IEEE transactions on pattern analysis and machine intelligence|volume=27|issue=8|pages=1239–1253|doi=10.1109/TPAMI.2005.161|issn=0162-8828|pmid=16119263}}</ref> to arbitrary sampling probabilities by viewing it as a [[Metropolis–Hastings algorithm]] and computing the acceptance probability of the proposed Monte Carlo move.

== Motivation ==

Line 8:

== Description ==

{{Main|Random cluster model}}

The algorithm is non-local in the sense that a single sweep updates a collection of spin variables based on the [[Random cluster model|Fortuin-Kasteleyn representation]]. The update is done on a "cluster" of spin variables connected by open bond variables that are generated through a [[Percolation theory|percolation]] process, based on the interaction states of the spins.

Consider a typical ferromagnetic Ising model with only nearest-neighbor interaction.

Line 53:

== Correctness ==

It can be shown that this algorithm leads to equilibrium configurations. To show this, we interpret the algorithm as a [[Markov chain]], and show that the chain is both [[Ergodicity|ergodic]] (when used together with other algorithms) and satisfies [[detailed balance]], such that the equilibrium [[Boltzmann distribution]] is equal to the [[stationary distribution]] of the chain.

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> Thus in practice, the SW algorithm is usually used in conjunction with single spin-flip algorithms such as the Metropolis-Hastings algorithm to achieve ergodicity.

Line 79:

==References==

{{Reflist}}

*{{cite journal | last1=Swendsen | first1=Robert H. | last2=Wang | first2=Jian-Sheng | title=Nonuniversal critical dynamics in Monte Carlo simulations | journal=Physical Review Letters | publisher=American Physical Society (APS) | volume=58 | issue=2 | date=1987-01-12 | issn=0031-9007 | doi=10.1103/physrevlett.58.86 | pages=86–88| pmid=10034599 | bibcode=1987PhRvL..58...86S }}

*Kasteleyn P. W. and Fortuin (1969) J. Phys. Soc. Jpn. Suppl. 26s:11