Swendsen–Wang algorithm: Difference between revisions

Revision as of 15:50, 4 May 2019

Revision as of 15:54, 4 May 2019

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 (2005) to arbitrary sampling probabilities by viewing it as a [[Metropolis–Hastings algorithm]] and computing the acceptance probability of the proposed Monte Carlo move.

== 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 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.

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 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 in a single sweep of moves a collective update of the spin variables of the system is done. The key idea is to take an additional number of 'bond' variables, as suggested by Fortuin and Kasteleyn, who mapped the Potts model onto a [[Percolation theory|percolation]] model via the [[random cluster model]].

Let's consider a typical ferromagnetic Ising model with only nearest-neighbourneighbor 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> there is no link between the sites <math>n</math> and <math>m</math>; if <math>b_{n,m}=1</math>, <math>\sigma_n</math> and <math>\sigma_m</math> are connected. These values are assigned according to the following (conditional) probability distribution:

Line 24:

<math>H[\sigma]=\sum\limits_{<i,j>}-J_{i,j}\sigma_i\sigma_j</math>,

and the [[Partition function (statistical mechanics)|partition function]] is

<math>Z=\sum\limits_{\lbrace\sigma\rbrace}e^{-\beta H[\sigma]}</math>.

Consider the interaction between a pair of selected sites <math>n</math> and <math>m</math> and eliminate it from the total Hamiltonian, defining

Line 66 ⟶ 68:

The algorithm is not efficient in simulating [[Geometrical frustration|frustrated systems]].

== See Also ==

* [[Random cluster model]]

* [[Monte Carlo method]]

*[ http://www.hpjava.org/theses/shko/thesis_paper/node69.html]

*[http://www-fcs.acs.i.kyoto-u.ac.jp/~harada/monte-en.html]

==References==

Line 72 ⟶ 81:

*Wang J.-S. and Swendsen, R. H. (1990),''Cluster Monte Carlo algorithms,'' Physica A 167:565.

*Barbu, A., Zhu, S. C. (2005), ''Generalizing Swendsen-Wang to sampling arbitrary posterior probabilities'', IEEE Trans Patt. Anal. Mach. Intell., 27(8):1239-1253.

==External links==

*[http://www.hpjava.org/theses/shko/thesis_paper/node69.html]

*[http://www-fcs.acs.i.kyoto-u.ac.jp/~harada/monte-en.html]

{{DEFAULTSORT:Swendsen-Wang algorithm}}

[[Category:Monte Carlo methods]]

[[Category:Statistical mechanics]]

[[Category:Critical phenomena]]

[[Category:Phase transitions]]