% -- LATEX --
\documentstyle{article}
\pagestyle{empty}

\begin{document}

\bigskip
\centerline{\bf The Potts model}

\bigskip
\centerline{Clive F. Baillie and Paul D. Coddington}\

\bigskip
The $q$-state Potts model \cite{Potts:52a} consists of a lattice of spins 
$\sigma_{i}$ which can take $q$ different values, and whose Hamiltonian is
$$ 
H = K \sum_{<i,j>} \delta_{\sigma_{i}\sigma_{j}} .
$$
For $q=2$ this is equivalent to the Ising model. The Potts model is thus a 
simple extension of the Ising model, however it has a much richer phase 
structure, which makes it an important testing ground for new theories and
algorithms in the study of critical phenomena \cite{Wu:82a}. 

Monte Carlo simulations of Potts models have traditionally used local 
algorithms such as that of Metropolis {\it et al.} \cite{Metropolis:53a},
however these algorithms have the major drawback that near a phase transition 
the autocorrelation time (the number of sweeps needed to generate a 
statistically independent configuration) increases 
approximately as $L^2$, where $L$ is the linear size of the lattice. 
New algorithms have recently been developed which dramatically reduce this
``critical slowing down'' by updating clusters of spins at a time (these 
algorithms are described in Section IV.3).
The original cluster algorithm of Swendsen and Wang was implemented for the 
Potts model \cite{Swendsen:87a}, and there is a lot of interest in how
well cluster algorithms perform for this model. At present there are
very few theoretical results known about cluster algorithms, and theoretical 
advances are most likely to come from first studying the simplest possible
models.

We have made a high statistics study of the SW algorithm and the single cluster
Wolff algorithm \cite{Wolff:89a}, as well
as a number of variants of these algorithms, for the $q=2$ and $q=3$ Potts 
models in two dimensions \cite{Baillie:89l}. 
We measured the autocorrelation time $\tau$ in the energy (a local operator) 
and the magnetization (a global one) on lattice sizes from $8^2$ to $512^2$. 
About 10 million sweeps were required for each lattice size in order to
measure autocorrelation times to within about 1\%.
From these values we can extract the
dynamical critical exponent $z$, given by $\tau(L) \sim L^{z}$, where $\tau(L)$
is measured at the infinite volume critical point (which is known exactly for 
the $2D$ Potts model). 

The simulations were performed on a number of different parallel computers. 
For lattice sizes of $128^2$ or less, it is possible to run independent
simulations on each processor of a parallel machine, enabling us to obtain
100\% efficiency by running 10 or 20 runs for each lattice size in parallel.
These calculations were done using a 32 processor Meiko Computing Surface,
a 20 processor Sequent Symmetry, a 20 processor Encore Multimax, and
a 96 processor BBN GP1000 Butterfly, as well as a network of SUN workstations,
and took approximately 15000 processor-hours.
For the largest lattice sizes, $256^2$ and $512^2$, a parallel cluster
algorithm was required, due to the large amount of calculation (and memory)
required. We have used the self-labeling algorithm described in Section IV.3,
which gives fairly good efficiencies of about 70\% on the machines we have 
used (an NCUBE-1 and a Symult S2010), by doing multiple runs of 32 nodes each 
for the $256^2$ lattice, and 64 nodes for $512^2$. Since this problem does not
vectorize, using all 512 nodes of the 
NCUBE gives a performance approximately five times that of a single processor
CRAY X-MP, while all 192 nodes of the Symult is equivalent to about six CRAYs.
The calculations on these machines have so far taken about 1000 hours.

Results for the autocorrelation times of the energy for the Wolff and
SW algorithms are shown in Fig. 1 for $q=2$ and Fig. 2 for $q=3$.
We do not yet have sufficient statistics on the $512^2$ lattice to extract
reliable results, so only data for lattice sizes up to $256^2$ 
are shown. As can be seen, the Wolff algorithm has smaller autocorrelation
times than SW, however the dynamical critical exponents for the two 
algorithms appear to be identical, being approximately 0.26(1) and 0.56(1) 
for $q=2$ and $q=3$ respectively, compared to values of approximately 2 for 
the standard Metropolis algorithm. 

Burkitt and Heermann \cite{Burkitt:89a}
% {D.W. Heermann and A.N. Burkitt, ``System Size Dependence of 
% the Autocorrelation Time for the Swendsen-Wang Ising Model'',
% Wuppertal preprint WU B 89-25, 1989}
have suggested that the increase in the autocorrelation time is logarithmic
rather than power law for the $q=2$ case (the Ising model), i.e. $z = 0$.
It is very difficult to distinguish between a logarithm and a small power.
We still do not have enough data to decide the matter conclusively, 
although we will soon have enough statistics to extract reliable numbers for a 
lattice of size $512^2$, which should allow us to distinguish between the two 
possibilities. 
In any case, the performance of the cluster algorithms for the Potts model 
is quite extraordinary, with autocorrelation times for the $256^2$ lattice 
which are hundreds of times smaller than for the Metropolis algorithm.
In the future we hope to use the cluster algorithms to perform greatly improved
Monte Carlo simulations of various Potts models, to study their critical 
behavior.

\bibliography{/home/swan/kea/bib/doc.bib,/home/swan/kea/bib/outside.bib,/home/swan/kea/bib/spcp.bib}
\bibliographystyle{/usr/lib/publisher/inputs/ccsf_sort}

\end{document}
