The Swendsen-Wang Cluster Algorithm

The previous Metropolis algorithm can perform poorly because the updates are local, that is, one spin at a time is updated. It doesn't always do badly--only near critical points where correlation length (correlations between spins) and correlation time (correlations between successive Monte Carlo configurations) both diverge in an infinite system. Cluster algorithms avoid this problem because clusters can be very large, of the same order as the correlation length. They use a clever way of finding large clusters of sites that can be updated at once.

Cluster algorithms were proposed by Swendsen and Wang [#!SW!#] in 1987, for Potts spin models. They have since been generalized to other models, and other algorithms. In the Swendsen-Wang algorithm, clusters of spins are created by introducing bonds between neighboring spins with probability

$$P(\sigma_i,\sigma_j) = 1 - \exp^{-\beta}$$ (6.10)

if the two spins are the same, and zero if they are not. All such clusters are generated and then updated by choosing a random new spin value for each cluster and assigning it to all the spins in that cluster.

A slightly different cluster algorithm has been proposed by Wolff [#!WOLFF!#]. In the Swendsen-Wang algorithm, we generated many clusters and then flip these clusters. In Wolff algorithm, a spin is chosen at random and a single cluster constructed around it, using same bond probabilities as for the Swendsen-Wang algorithm. All the spins in this cluster are then flipped, i.e, changed to a random new spin different from the old one. These parallel Wolff cluster algorithms were developed in several different languages including C code for the CM-5 using CMMD [#!CMMD!#] which was presented in [#!BAE!#].

Cluster algorithms have in common the problem of identifying and labeling the connected clusters of spins. This is very similar to an important problem in image processing, that of identifying and labeling the connected components in a binary or multi-colored image composed of an array of pixels. The only real difference is that in the spin model case, neighboring sites of the same spin have a certain probability of being in the same cluster, while for neighboring pixels of the same color that probability is one. Unfortunately this is a large enough difference so that some algorithms which work in image analysis will not work, or require substantial changes, for spin models. In our implementation of the Swendsen-Wang cluster algorithm for the Ising model, we have used a commonly used cluster identification algorithm invented by Hoshen and Kopelman.

Figure 6.4: The Main Procedure of Sequential Swendsen-Wang Algorithm.