Content deleted Content added
m Open access bot: hdl added to citation with #oabot. |
Citation bot (talk | contribs) Added bibcode. | Use this bot. Report bugs. | Suggested by Abductive | Category:Monte Carlo methods | #UCB_Category 21/65 |
||
| (8 intermediate revisions by 6 users not shown) | |||
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|
== Motivation ==
The problem of the critical slowing-down affecting local processes is of fundamental importance in the study of second-order [[phase transition]]s (like ferromagnetic transition in the [[Ising model]]), as increasing the size of the system in order to reduce finite-size effects has the disadvantage of requiring a far larger number of moves to reach thermal equilibrium. Indeed the correlation time <math>\tau</math> usually increases as <math>L^z</math> with <math>z\simeq 2</math> or greater; since, to be accurate, the simulation time must be <math>t\gg\tau</math>, this is a major limitation in the size of the systems that can be studied through [[Local algorithm|local algorithms]]. SW algorithm was the first to produce unusually small values for the dynamical critical exponents: <math>z=0.35</math> for the 2D Ising model (<math>z=2.125</math> for standard simulations); <math>z=0.75</math> for the 3D Ising model, as opposed to <math>z=2.0</math> for standard simulations.
== 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|
Consider a typical ferromagnetic Ising model with only nearest-neighbor interaction.
Line 55:
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|
The SW algorithm does however satisfy detailed-balance. To show this, we note that every transition between two Ising spin states 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
Line 67:
== 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|
== Generalizations ==
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|
The first approach is to extend the bond-formation rules to more non-local cells, and the second approach is to generate clusters based on more relevant order parameters. In the first case, we have the [[KBD algorithm]] for the [[Domino tiling|fully-frustrated Ising model]], where the decision of opening bonds are made on each plaquette, arranged in a checkerboard pattern on the square lattice.<ref>{{Cite journal|
== See also ==
Line 86:
*{{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
*{{cite journal | last1=Fortuin | first1=C.M. | last2=Kasteleyn | first2=P.W. | title=On the random-cluster model | journal=Physica | publisher=Elsevier BV | volume=57 | issue=4 | year=1972 | issn=0031-8914 | doi=10.1016/0031-8914(72)90045-6 | pages=536–564| bibcode=1972Phy....57..536F }}
*{{cite journal | last1=Wang | first1=Jian-Sheng | last2=Swendsen | first2=Robert H. | title=Cluster Monte Carlo algorithms | journal=Physica A: Statistical Mechanics and Its Applications | publisher=Elsevier BV | volume=167 | issue=3 | year=1990 | issn=0378-4371 | doi=10.1016/0378-4371(90)90275-w | pages=565–579| bibcode=1990PhyA..167..565W }}
*{{cite journal | last=Barbu | first=A. | title=Generalizing Swendsen-Wang to sampling arbitrary posterior probabilities | journal=IEEE Transactions on Pattern Analysis and Machine Intelligence | publisher=Institute of Electrical and Electronics Engineers (IEEE) | volume=27 | issue=8 | year=2005 | issn=0162-8828 | doi=10.1109/tpami.2005.161 | pages=1239–1253| pmid=16119263 | bibcode=2005ITPAM..27.1239B | s2cid=410716 }}
{{DEFAULTSORT:Swendsen-Wang algorithm}}
| |||