The Swendsen–Wang algorithm is the first non-local or cluster algorithm for Monte Carlo simulation for large systems near criticality.
It has been introduced by Robert Swendsen and Jian-Sheng Wang in 1987 at Carnegie Mellon.
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.
It has been generalized by Barbu and Zhu[1] to arbitrary sampling probabilities by viewing it as a Metropolis–Hastings algorithm and computing the acceptance probability of the proposed Monte Carlo move.
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.
, 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:
The algorithm is non-local in the sense that a single sweep updates a collection of spin variables based on the Fortuin–Kasteleyn representation.
The update is done on a "cluster" of spin variables connected by open bond variables that are generated through a percolation process, based on the interaction states of the spins.
Consider a typical ferromagnetic Ising model with only nearest-neighbor interaction.
This probability distribution has been derived in the following way: the Hamiltonian of the Ising model is
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:
The process can be easily adapted to antiferromagnetic spin systems, as it is sufficient to eliminate
(as suggested by the change of sign in the interaction constant).
It can be shown that this algorithm leads to equilibrium configurations.
To show this, we interpret the algorithm as a Markov chain, and show that the chain is both ergodic (when used together with other algorithms) and satisfies detailed balance, such that the equilibrium Boltzmann distribution is equal to the stationary distribution of the chain.
Ergodicity means that it is possible to transit from any initial state to any final state with a finite number of updates.
It has been shown that the SW algorithm is not ergodic in general (in the thermodynamic limit).
To show this, we note that every transition between two Ising spin states 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
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
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.
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 (
) is that the correlation length divergence is strictly related to the formation of percolation clusters, which are flipped together.
[3] Some mathematically rigorous results on the mixing time of this process have been obtained by Guo and Jerrum [1].
The algorithm is not efficient in simulating frustrated systems, because the correlation length of the clusters is larger than the correlation length of the spin model in the presence of frustrated interactions.
[4] Currently, there are two main approaches to addressing this problem, such that the efficiency of cluster algorithms is extended to frustrated systems.
The first approach is to extend the bond-formation rules to more non-local cells, and the second approach is to generate clusters based on more relevant order parameters.
In the first case, we have the KBD algorithm for the fully-frustrated Ising model, where the decision of opening bonds are made on each plaquette, arranged in a checkerboard pattern on the square lattice.
[5] In the second case, we have replica cluster move for low-dimensional spin glasses, where the clusters are generated based on spin overlaps, which is believed to be the relevant order parameter.