Content deleted Content added
Line 1:
The '''Swendsen–Wang algorithm''' is the first non-local [[algorithm]] for [[Monte Carlo simulation]] for large systems near criticality.
The original algorithm was designed for the 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. A key ingredient is the 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 [[
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.
Line 36 ⟶ 35:
Since the first term contains a restriction on the spin values whereas there is no restriction in the second term, the weighting factors (properly normalized) can be interpreted as probabilities of forming/not forming a link between the sites: <math>P_{<n,m>\;link}=1-e^{-2\beta J_{nm}}.</math>
The process can be easily adapted to antiferromagnetic spin systems, as it is sufficient to eliminate <math>Z_{n,m}^{same}</math> in favor of <math>Z_{n,m}^{diff}</math> (as suggested by the change of sign in the interaction constant).
* After assigning the bond variables, we identify the same-spin clusters formed by connected sites and make an inversion of all the variables in the cluster with probability 1/2. At the following time step we have a new starting Ising configuration, which will produce a new clustering and a new collective spin-flip.
== Correctness ==
It can be shown that this algorithm leads to equilibrium configurations. The first way to prove it is using the theory of [[Markov chain
Alternatively, we can show explicitily 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 53 ⟶ 51:
== 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.
The algorithm is not efficient in simulating [[Geometrical frustration|frustrated systems]].
Line 59 ⟶ 57:
==References==
*Swendsen, R. H., and Wang, J.-S. (1987), ''Nonuniversal critical dynamics in Monte Carlo simulations'', Phys. Rev. Lett., 58(2):86–88.
*Kasteleyn P. W. and Fortuin (1969) J. Phys. Soc. Jpn. Suppl. 26s:11; Fortuin C. M. and Kasteleyn P.W. (1972), Physica
*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.
Line 70 ⟶ 68:
[[Category:Monte Carlo methods]]
[[Category:Statistical mechanics]]
| |||