\newbox\leftpage
\newdimen\fullhsize 
\newdimen\hstitle
\newdimen\hsbody
\tolerance=1000\hfuzz=2pt
\magnification=\magstep2
\baselineskip=14pt

\font\bfbigger=cmbx10 scaled\magstep2
\font\small=cmr8
\font\itsmall=cmti8

\nopagenumbers

\noindent
\centerline{\bfbigger PHYSICS ALGORITHMS}
\bigskip

\bigskip
\noindent
{$\bullet$} {\bf Spin Models of Magnets}
\medskip

Some materials become magnetized due to interactions between
the spins of electrons. 
These materials can have a {\it phase transition} between a
low temperature magnetized phase, where the spins tend to be aligned 
(or ordered), and a high temperature unmagnetized phase, where the 
spins are disordered. 
% \smallskip

The behavior at this phase transition can be well described 
by very simple models of interacting spins on a lattice, such as
the Potts model, where the spins are in discrete states. 
In the pictures above, we show examples of 2 and 3 state Potts models, 
where the different spin states are represented by different colors.

\bigskip
\noindent
{$\bullet$} {\bf Numerical Simulations}
\medskip

Numerical calculations are very important to the study of spin models, and 
are usually done by Monte Carlo simulation, using the standard Metropolis 
algorithm, which is used for simulation and optimization in many fields of 
science.
% \smallskip

To get realistic results, we need to use large lattices.
At the phase transition, the number of Metropolis iterations needed 
to generate a statistically independent data value grows roughly as the 
square of the lattice size, so the calculation quickly becomes 
computationally intractible. This is known as {\it critical slowing down}. 

\bigskip
\noindent
{$\bullet$} {\bf Cluster Algorithms}
\medskip

Recently introduced {\it cluster algorithms} drastically reduce critical
slowing down, since they make large, non-local changes to the system,
rather than the local changes of the Metropolis algorithm.
These multi-scale algorithms are also much more closely related to the 
physics of the model than the Metropolis algorithm.
% \smallskip

The algorithm due to Wolff starts at a random site, and creates bonds
between neighboring sites with a certain probability. This makes a 
cluster of bonded sites (Fig. 1), for which all the spins can be
changed at once. 
The Swendsen-Wang algorithm finds all such clusters in the lattice, and
updates them. The boundaries of the clusters are shown in black in Fig. 3. 

\bigskip
\noindent
{$\bullet$} {\bf Current Research}
\medskip

Cluster algorithms can be generalized to other models, but it is
not known how to apply them to any given spin model, or to similar 
problems such as lattice gauge theory, which is the numerical study of 
the fundamental forces of nature.
% \smallskip

Some progress has been made on models for which critical slowing down is
severe, such as spin glasses and frustrated systems (Fig. 2), and this 
is currently one of our main areas of research. 
% \smallskip

\bigskip
\noindent
{$\bullet$} {\bf Optimization}
\medskip

Finding the ground state of a spin glass is a classic NP-complete
optimization problem, and better algorithms for this system may 
provide insight into how to improve physical optimization schemes such as 
simulated annealing, which currently use the Metropolis algorithm.

\bigskip
\noindent
{$\bullet$} {\bf References}
\medskip

{\small

\noindent
\item{[1]} P.D. Coddington and C.F. Baillie,
{\itsmall A Comparison of Cluster Algorithms for Potts Models},
Proc. of the 1989 Symposium on Lattice Field Theory, Capri (Sept. 1989),
Nucl. Phys. B (Proc. Suppl.) 17, 305 (1990).

\noindent
\item{[2]} C.F. Baillie and P.D. Coddington,
{\itsmall Comparison of Cluster Algorithms for 2-D Potts Models},
Phys. Rev. B 43, 10617 (1991).

\noindent
\item{[3]} P.D. Coddington and C.F. Baillie,
{\itsmall Empirical relations between static and dynamic exponents for
Ising model cluster algorithms},
submitted to Phys. Rev. Lett.

}

\vfill
\end
