Swendsen–Wang algorithm
The Swendsen–Wang algorithm is an algorithm for Monte Carlo simulation of the Ising model in which the entire sample is divided into same-spin clusters. Each cluster is then assigned a new random spin value. Compare the Wolff algorithm.
It is one of the first algorithms based on global changes to the system in a single sweep of moves. The original algorithm was designed for the Ising and Potts models, and later it was generalized to other systems as well, such as the XY model by Wolff algorithm and particles of fluids. A key ingredient of the method is based on the representation of the Ising or Potts model through percolation models of connecting bonds due to Fortuin and Kasteleyn. These bonds form so-called clusters. Nearest sites of equal-spins are joined together by the bonds with a probability, P=1-exp(-2J/(kBT)), where J is the coupling constant for the ferromagnetic Ising model, T is temperature, and kB is Boltzmann constant. The clusters are then “flipped” together with equal probabilities. The method is most efficient near a second-order phase transition point, overcoming the critical slowing down.
It has been generalized by Barbu and Zhu (2005) to sampling arbitrary probabilities by viewing it as a Metropolis–Hastings algorithm and computing the acceptance probability of the proposed Monte Carlo move.
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 (Utrecht) 57:536.
- 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.