Swendsen–Wang algorithm: Difference between revisions

Revision as of 14:41, 18 April 2024

Revision as of 10:38, 28 April 2024

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|last1=Edwards|first1=Robert G.|last2=Sokal|first2=Alan D.|date=1988-09-15|title=Generalization of the Fortuin-Kasteleyn-Swendsen-Wang representation and Monte Carlo algorithm|url=https://link.aps.org/doi/10.1103/PhysRevD.38.2009|journal=Physical Review D|volume=38|issue=6|pages=2009–2012|doi=10.1103/PhysRevD.38.2009|pmid=9959355|bibcode=1988PhRvD..38.2009E}}</ref>. Some mathematically rigorous results on the mixing time of this process have been obtained by Guo and Jerrum [https://projecteuclid.org/journals/annals-of-applied-probability/volume-28/issue-2/Random-cluster-dynamics-for-the-Ising-model-is-rapidly-mixing/10.1214/17-AAP1335.full].

== Generalizations ==