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

\noindent
{\bf NEW UPDATE ALGORITHMS FOR SPIN MODELS}

Clive Baillie and Paul Coddington.

In a Monte Carlo simulation of a lattice spin or gauge model, each iteration
produces a new configuration on which measurements can be made. These 
configurations are generally correlated, so in practice it is only useful
to make measurements every $\tau$ iterations, where $\tau$ is the 
autocorrelation length. It can be shown that $\tau \sim \xi^{z}$, where 
$\xi$ is the correlation length and $z$ is called the dynamical critical 
exponent. For the usual local update algorithms, such as the Metropolis
algorithm, $z$ is approximately 2. This is a major problem for simulations
near a critical point, since as we increase the lattice size, the
correlation length tends to infinity, and thus $\tau$ rapidly gets too large
to allow the generation of a reasonable number of independent configurations.
This phenomenon is known as {\it critical slowing down}. 

Non-local updating schemes which can dramatically reduce critical slowing
down have recently been introduced by Swendsen and Wang 
\ref\SW{R.H. Swendsen and J.-S. Wang, Phys. Rev. Lett. {\bf 58}, 86 (1987)}
and by Wolff 
\ref\Wolff{U. Wolff, Phys. Rev. Lett. {\bf 62}, 361 (1989)}.
These algorithms involve the creation of clusters of spins, using simple 
probability functions to connect neighboring spins together to form clusters,
which are closely tied to the clusters found in percolation models. Cluster
update algorithms for spin models generally have dynamical exponents of
less than one, and in some cases (such as the 2-d Ising and XY models) they
are believed to be zero.
We have performed high statistics runs on 2-d Potts models in order to 
compare the algorithms of Wolff and Swendsen and Wang, as well as variants
of these algorithms, by obtaining accurate values of the autocorrelation 
lengths and dynamical critical exponents 
\ref\us{C.F. Baillie and P.D. Coddington, ``A Comparison of Cluster 
Algorithms for Potts Models'', CCCP Report 835, in preparation}.
This has been done on a number of parallel computers, 
using the trivial but very efficient technique of
doing a different run on each processor, and then combining the results.

Recently we have also been investigating parallel algorithms for cluster
updating. Unfortunately the quality of non-locality which makes these 
cluster algorithms so useful, also makes them very difficult to parallelize
efficiently, since this involves a large amount of non-local communication.
SIMD algorithms for identifying and labelling clusters have
been proposed in the past in connection with percolation models 
\ref\DAP{R. Dewar and C.K. Harris, J. Phys. A {\bf 20} 985 (1987)}
and image analysis 
\ref\TMC{W. Lim, A. Agrawal, L. Nekludova, ``A Fast Parallel Algorithm for
Labelling Connected Components in Image Arrays'' Thinking Machines
Corporation Technical Report NA86-2}.
Because of the highly irregular nature of the clusters, it seems that a 
good MIMD algorithm should do better than these algorithms,
however so far the only parallel algorithm used on a MIMD machine has 
proved to be very inefficient for more than a few processors
\ref\Burkitt{A.N. Burkitt and D.W. Heermann, Comp. Phys. Comm. {\bf 54}
210 (1989)}.
We are currently engaged in testing the old SIMD algorithms on the AMT DAP
and the TMC Connection Machine, and attempting to come up with a better 
MIMD algorithm to run on hypercubes and transputer arrays.

\listrefs\vfill
\end
