The Swendsen–Wang algorithm is the first non-local algorithm for Monte Carlo simulation for large systems near criticality.
Contents
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. 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.
Motivation
The problem of the critical slowing-down affecting local processes is of fundamental importance in the study of second-order phase transitions (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
Description
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 model.
Let's consider a typical ferromagnetic Ising model with only nearest-neighbour interaction.
where
This probability distribution has been derived in the following way: the Hamiltonian of the Ising model is
Introduce the quantity
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:
Correctness
It can be shown that this algorithm leads to equilibrium configurations. The first way to prove it is using the theory of Markov chains, either noting that the equilibrium (described by Boltzmann-Gibbs distribution) maps into itself, or showing that in a single sweep of the lattice there is a non-zero probability of going from any state of the Markov chain to any other; thus the corresponding irreducible ergodic Markov chain has an asymptotic probability distribution satisfying detailed balance.
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
since
This is valid for every bond configuration the system can pass through during its evolution, so detailed balance is satisfied for the total transition probability. This proves that the algorithm works.
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 (
The algorithm is not particularly good for simulating frustrated systems.