\input   mac.tex
\input   moremac.tex
\input peqns.tex

\noindent
{\it Introduction}
Cluster algorithms became important for spin models when Swendsen and Wang (SW)
published their algorithm for Potts models
\ref\SW{R. H. Swendsen and J.-S. Wang, \PRL{58}, 86 (1987)}.
This is based on an equivalence between configurations of Potts spins and
configurations of clusters in a percolation problem, which was discovered by
Kasteleyn and Fortuin some time ago
\ref\KF{P. W. Kasteleyn and C. M. Fortuin, {\it J. Phys. Soc. Jpn. Suppl.} {\bf 26s},
11 (1969); C. M. Fortuin and P. W. Kasteleyn, {\it Physica} {\bf 57}, 536 (1972)}.
Sweeny \ref\Sweeny{M. Sweeny, \PRB{27}, 4445 (1983)} also noticed
Kasteleyn and Fortuin's work and came up with a different algorithm for simulating the
q-state Potts model for arbitrary (even non-integer) q. He achieved this by
simulating the equivalent percolation clusters. However, Sweeny's algorithm is complicated
to program and is restricted to two dimensions, whereas SW is relatively easy to program and
works in any dimension (but only for integer q). Moreover, SW has been quickly taken up and
generalized to continuous spin models by Niedermayer and Wolff (see below).
We shall firstly describe SW and summarize applications of it, then outline
Niedermayer, and finally concentrate on Wolff as it shows the most promise.

To explain SW, we begin with the partition function for the Potts model
$$Z = Tr_{\{\sigma\}} e^{\beta \sum_{<ij>} (\delta_{\sigma_i,\sigma_j} - 1)}. \eqn\EqSWo$$
We map it onto a general percolation model {\it \`a la} Kasteleyn and Fortuin, as
follows.
Firstly remove the interaction between sites $l$ and $m$
$$S_{l,m} = \beta \sum_{<i,j> \not= <l,m>} (\delta_{\sigma_i,\sigma_j} - 1). \eqno\eq$$
Then define the restricted sums
$$Z_{l,m}^{same} = Tr_{\{\sigma\}} e^{S_{l,m}} \delta_{\sigma_l,\sigma_m} \eqno\eq$$
and
$$Z_{l,m}^{diff} = Tr_{\{\sigma\}} e^{S_{l,m}} (1 - \delta_{\sigma_l,\sigma_m}) \eqno\eq$$
so that
$$Z = Z_{l,m}^{same} + e^{-\beta} Z_{l,m}^{diff}. \eqn\EqSWt$$
Now introduce
$$Z_{l,m}^{indep} = Tr_{\{\sigma\}} e^{S_{l,m}} = Z_{l,m}^{same} + Z_{l,m}^{diff}. \eqno\eq$$
and rewrite \EqSWt\ as
$$Z = (1 - e^{-\beta}) Z_{l,m}^{same} + e^{-\beta} Z_{l,m}^{indep}. \eqno\eq$$
Since the first term contains the restriction that the spins on sites $l$ and $m$ are
the same, and the second term places no restrictions on the spins, the weighting
factors can be interpreted in terms of the probability $p = 1 - e^{-\beta}$ of a
bond between the two sites.
This procedure is repeated for all interactions in \EqSWo\ giving a configuration of
bonds, from which clusters are formed. For each cluster, all the spins are in one of the
q states independently of the states of the other clusters. If there are $N_c$ clusters,
this gives Kasteleyn and Fortuin's result
$$Z = Tr_{\{bonds\}} p^b (1-p)^n q^{N_c}, \eqno\eq$$
where $b$ is the number of bonds and $n$ is the number of interactions that do not form
a bond. Thus we have represented the spin system as a configuration of bonds forming
clusters. Notice that some of the original clusters of spins may be split into
smaller clusters, since bonds occur only with probability $p = 1 - e^{-\beta}$ between
sites with the same spin.
SW's algorithm consists of assigning a new random Potts spin value to each cluster
independently, with all the sites in the cluster getting this value.
By erasing bonds we are left with a new Potts spin configuration. This new
configuration can differ substantially from the original one since large clusters
can be changed in a single step. Thus we have achieved a nonlocal move which is what is
required to reduce CSD. SW \SW\ demonstrate that their algorithm satisfies detailed
balance.

Wolff \ref\W{U. Wolff, \PRL{62}, 361 (1989)} generalized SW for O(N) models by inventing
an appropriate spin flip operation. Consider the O(N) model partition function
$$Z = Tr_{\{{\bf\sigma}\}} e^{\beta \sum_{<ij>} {\bf\sigma_i . \sigma_j}}, \eqno\eq$$
where ${\bf\sigma_i}$ are unit vectors in $\Re^N$.
Generalize the spin flip operation $\sigma_i \rightarrow -\sigma_i$ for the Ising model
($N=1$) in the following way. For $N \geq 2$ and any ${\bf r} \in S_{N-1}$ define
the generalized spin flip as the reflection of ${\bf\sigma_i}$ with respect to the
hyperplane orthogonal to ${\bf r}$:
$${\bf R}({\bf r}){\bf\sigma_i} = {\bf\sigma_i} - 2 ({\bf\sigma_i . r}){\bf r}. \eqn\EqWo$$
Clearly, the action is invariant under this global ${\bf R}$ transformation since
$$[{\bf R}({\bf r}){\bf\sigma_i}] . [{\bf R}({\bf r}){\bf\sigma_j}] =
{\bf\sigma_i . \sigma_j}. \eqno\eq$$
An elementary cluster update consists of the following steps
\medskip
\item{i.} choose random reflection ${\bf r} \in S_{N-1}$ and random site $i$ as first
point of cluster $c$ to be built
\smallskip
\item{ii.} flip ${\bf\sigma_i} \rightarrow {\bf R}({\bf\sigma_i})$ and mark $i$
\smallskip
\item{iii.} visit all links $l$ connecting $i \in c$ to its nearest neighbors $j$ and
activate bond $l = <ij>$ with probability
$$\eqalign{p({\bf\sigma_i,\sigma_j})
&=\ 1 - e^{min[0,\beta{\bf\sigma_i}.({\bf 1 - R}({\bf r})){\bf\sigma_j}]}\cr
&=\ 1 - e^{min[0,-2\beta({\bf r.\sigma_i})({\bf r.\sigma_j})]}\cr
}\eqn\EqWt$$
and if this happens ${\bf \sigma_j}$ is flipped, and $j$ is marked and joined to $c$
\item{iii.} continue iteratively for all bonds leading to unmarked neighbors of
newly adjoined sites until process stops
\medskip
\noindent
Wolff \W\ shows that this satisfies detailed balance.

For the Ising case the bond activation probabilities are the same as in SW:
$p = 1 - e^{-2\beta}$ for parallel spins and $p = 0$ for antiparallel ones.
The connection between the two algorithms can be made clearer by consideration
of a less efficient but equivalent implementation of Wolff's algorithm.
This consists of first activating all bonds of the lattice with the
appropriate probabilities and decomposing all the sites into clusters. These
are the SW clusters. Then flip each cluster independently with probability
${1 \over 2}$, rather than selecting one cluster and flipping it alone.

The adequacy of discrete flips for continuous spin models is ensured because the
axis of reflection is chosen randomly.
If we choose ${\bf r}$ and build a cluster in a region where spins are nearly
orthogonal to ${\bf r}$ then \EqWo\ is a small deformation and bond probabilities
\EqWt\ typically lead to small clusters. On the other hand, if ${\bf r}$ is
parallel or antiparallel to the local spin direction then the cluster tends to
grow until it reaches an energetically acceptable surface -- thus mimicking
real clusters.

\listrefs\vfill
\end
