Date: Thu, 1 Aug 91 14:13:03 EDT
From: st8 (Daniel Baumann)
Received: by sccs.syr.edu (4.1/1.0-6/5/90)
	id AA25867; Thu, 1 Aug 91 14:13:03 EDT
Message-Id: <9108011813.AA25867@sccs.syr.edu>
To: biham
Subject: New Revised Paper
Status: RO

\documentstyle{article}
\bibliographystyle{plain}
\pagestyle{empty}
\pagenumbering{arabic}
\hoffset -2.5 cm
\textwidth 17 cm
\textheight 22 cm
\footskip 1 cm
\topmargin -1cm
\baselineskip 24pt
\begin{document}
                         \vspace*{0 cm}
 \begin{center}
 \huge\bf The Visualization of Triangular Lattice Spin Models \\
                         \vspace{2.5 cm}
 \Large\sc Daniel Baumann\\
                         \medskip
\large\sf Computational Physics Research Undergraduate, Syracuse University \\


                         \vspace{1.2 cm}

\Large \sc Paul Coddington \\
                         \medskip
 \large\sf Physics Department, Syracuse University, Syracuse, NY, 13244\\
\end{center}

                         \vspace{2 cm}

 \begin{abstract}
 \noindent\normalsize
To adequately understand spin models it is certainly helpful to use
computer graphics to visualize the models.  For the particular case of a
triangular  lattice, we developed
a fast and friendly program in the C language using Xwindows graphics
to help  us study and
create new Monte Carlo updating techniques that are essential to the
simulating of spin models.
Both cases of ferromagnets and anti-ferromagnets were adapted with the
Metropolis, Wolff, Swendson-Wang and Plaquette updates featured.  From
the usage of this program we hope to develop new and improved updating
procedures, and to better understanding the present update schemes.   
 \end{abstract}

                           \vfill
\newpage
\large
\section{\bf Spin Models of Magnets}
\medskip

Some materials can become magnetized due to complex interactions between
the spins of electrons in the atoms of the material. At high temperatures
there is a transition between a magnetized phase, where the spins
tend to be aligned (or ordered), and an unmagnetized phase where the spins
are disordered. Surprisingly, the behavior at this ``critical'' temperature 
is well described by very simple models of interacting spins on a lattice.
A simple spin model is the Potts model\cite {potts}, where the spin
can be in Q  
different states. For the ferromagnetic model, the interaction between
the spins is that if two
neighboring spins are in the same state, they have a smaller energy ($E = -1$) 
than if they are in different states (in which case $E = 0$). Hence the 
spins tend to align, except when the temperature becomes high enough so that
the thermal energy causes the system to become disordered. This is similar 
to how heating a solid (an ordered state) will cause it to melt into a liquid 
(a disordered state).  Opposite of the ferromagnet is the
antiferromagnet.  In this model the energy values are swapped and two
 neighboring spins will try to
oppose eachother's spins.  The two state triangular lattice has a geometry such
that not all interacting spins can be opposite simultaneously and therefore
have the lowest energy.  For this reason it is called a frustrated system.

\bigskip
\section{\bf Numerical Calculations}
\medskip

In the simplest case of only two states, this system is
 known as the Ising 
model\cite {ising}, and has been solved exactly in two dimensions,
greatly enhancing our 
understanding of magnetic systems, and phase transitions in general. More 
complicated models cannot be solved analytically, and in many cases the most
accurate results come from computer simulations.

A quantity such as the magnetization $M$ (which measures what proportion of
the spins are aligned), is calculated as follows : 
% the spins are aligned), is calculated by taking the thermodynamic average
% at a given temperature (here $\beta$ is the inverse temperature) :
$$
% <M> = {\sum_C M(C) e^{-\beta E(C)} \over \sum_C e^{-\beta E(C)} },
<M> = {1 \over Z} \sum_C M(C) e^{-\beta E(C)}, \qquad \quad Z = \sum_C e^{-\beta E(C)},
$$
% The sum is over
where $\beta$ is the inverse temperature, and the sum is over
all possible configurations $C$ of the spins on the lattice. $M(C)$ and
$E(C)$ are the magnetization and energy of a given configuration. For a 
$Q$-state Potts model on a lattice of $V$ sites, the number of possible
configurations of spins is $Q^V$, so summing over all configurations is
infeasible for all but the smallest lattices. 

\bigskip
\section{\bf Monte Carlo Simulations}
\medskip

Instead we use a
method known as ``Monte Carlo'' simulation\cite {monte} (since it is a stochastic, 
non-deterministic procedure, like spinning a roulette wheel) to generate the
configurations which make important contributions to the above sum.
% 
This is done by generating each configuration with a probability given by
its Boltzmann weight $e^{-\beta E} / Z$.
The standard way of generating these configurations is the Metropolis
algorithm\cite {met}, which works as follows :
\medskip
\begin{itemize}
  \item Propose a random change to one of the spins.
  \item If this decreases the energy, accept the change.
  \item If the energy is increased, accept the change with probability
                $e^{-\beta (E_{new} - E_{old})}$. 
\end{itemize}
\medskip
\noindent
This algorithm has very wide applicability, and is used not just for spin 
models, but in the simulation of a huge variety of systems.

Measurements of any quantity (such as the magnetization) can then be made on
these configurations, and the average over configurations taken. This will be
an approximation to the true value, with the usual statistical error, which 
is proportional to $1/\sqrt N$. Here $N$ is the number of {\it statistically
independent} (i.e. uncorrelated) configurations. 

\bigskip
\section{\bf A Problem --- Critical Slowing Down}
\medskip

For standard
update algorithms, such as Metropolis, the configurations are generally
correlated over many iterations, especially near a phase transition. This
is because these algorithms are {\it local} (i.e. the method depends only 
on the neighbors of the spin to be updated), whereas at the critical 
temperature the spins are correlated over large distances. In fact, as we 
increase our lattice size $L$, the number of iterations needed to generate 
an independent configuration grows roughly as $L^2$, so the calculation
quickly becomes computationally intractable.
This is known as critical slowing down, and is a major problem for Monte 
Carlo simulations.

\bigskip
\section{\bf A Solution --- Cluster Algorithms}
\medskip

A non-local updating scheme which can dramatically reduce critical slowing
down has recently been introduced by Swendsen and Wang\cite {SW}.
Their algorithm  is
very simple -- if two neighboring spins are the same, a bond is placed 
between them with probability $1-e^{-\beta}$. This creates clusters of bonded
spins, and all the spins in a cluster can be changed to a value 
chosen at random for each cluster. A variation of this algorithm, due to 
Wolff\cite {W}, is to pick a site at random and generate a single cluster around it.
This will tend to produce larger clusters, and decorrelate the configurations
even faster.  For the same computational cost, the Metropolis algorithm 
changes the configuration only slightly, leaving the large scale structure 
intact, whereas the cluster algorithms both produce a completely different
configuration. 



\bigskip
\section{\bf Displaying Spin Models on Computers}
\medskip

By visualizing spin models we can better understand cluster
algorithms, and gain insight into new algorithms. Since computers are necessary
to perform simulations of spin models it is only natural to
utilize their graphics capabilities.  This is especially true when high-powered
workstations are available like the Sun Sparc Stations. XWindows was chosen
 for the graphics due to its portability, quickness and
high resolution.

For 2-dimensional lattice spin models, the sites can be mapped onto
the display with little effort and the scaling parameters added to
zoom inward and outward.  3-dimensional lattices are another case.
To adequately display them interactively would probably  require the
use of powerful Silicon Graphics Workstations creating translucensy and
three-dimensional images.  During this particular research project we
focused on the 2-dimensional lattices, in particular the triangular
lattice. 


\bigskip
\section{\bf The Triangular Lattice}
\medskip

To visualize spin models it is necessary to show what state or spin value
the different sites have for the particular lattice involved.  The sites are
located at the intersections in the lattice.  For example, a square
lattice has regularly spaced sites in rows and columns.  To see this,
imagine a screen on your window at home and wherever the wires
cross a site exists.  This is a bit more complicated when trying to
grasp a triangular lattice.

The sites for a triangular lattice spin model are located at the
intersections of a triangular grid (figure 1a), however the representation
 of the sites themselves are
not triangular, but hexagonal as figure 1b shows.  Each hexagon
represents one site in the model and is filled solid with a color depending on
its particular spin.  The result is that a triangular lattice appears
to be a grid of hexagons,  while the bonds between sites form the
triangular pattern one would expect to see (figure 1c).



\begin{figure}[h]

\vspace{3 in}

\caption{a) triangular grid \hspace {.5in} b) hexagonal grid of sites
\hspace {.5in} c) the sites on the grid}

\end{figure}




\medskip
\subsection{\bf A Rectangular Shaped Triangular Lattice}
\medskip    

It is convenient to display the triangular lattice such that the
overall shape is a rectangle.  In addition, rectangular arrays are convenient
for storing the values of the spins.  For this
particular project, the rectangle's dimensions ranged from 4x4 up to 128x128 sites.
Mapping the values of the sites in the array to the displayed
honeycomb of hexagons is a task all in itself.  It was decided
that the first column of the array would start in the upper left-hand
corner of the window and each column to its right would be shifted
down half the height of a hexagon.  The result is a grid of hexagons
whose top boundary slopes downward from left to right.  To fix this
slope, the hexagons cut off at the bottom of the window are
drawn at the top.  This accurately represents the system because the
rectangle is designed to be a torus in which case the bottom hexagons wrap
around to the top.  Likewise, the hexagons on the right wrap around to
the left.  Not only are the hexagons displayed as a torus, but
the communication between sites behaves in the same fashion.  To
further add to the torus effect, the bottom hexagons in the even
columns of the rectangle, which protrude below the bottom of the window, are cut in
half and drawn at the top of the display.  The same goes for the
hexagons in the right most column, who have a portion of them
displayed on the left.  Care must be taken in this case, however,
because if there are an odd number of columns the cut and pasting
does not have the desired affect and creates troublesome overlap.  Lastly, the
hexagon in the bottom right
corner is cut in two directions, and thus, into four pieces (figure 2).     

\begin{figure}[h]

\vspace{4.0 in}

\caption{A triangular lattice in a rectangular window}

\end{figure}

\medskip
\subsection{\bf Neighbors}
\medskip

The theory behind spin models is that the sites affect one another
depending on whether the spin values are similar or different.
Thus, to update a site or create bonds between a site and its neighbor it is
necessary to know what spins its neighbors have in relation to its
own.  For spin
models only the interactions with the nearest neighbors of a site are
necessary since the
influence of more distant sites is relatively non-existent.  Who a site's
closest neighbors are depends on what type of lattice the site is in.
For a square lattice the neighbors for the (i,j) site are {(i+1,j), 
(i-1,j), (i,j+1), (i,j-1)} (figure 3a).  The diagonal neighbors are
not influential enough to include.  On a triangular lattice, each site
has six neighbors.  These include the same four neighbors as above,
but also (i+1,j-1) and (i-1,j+1) (figure 3b).

\begin{figure}[h]

\vspace{2.4 in}

\caption{a) The neighbors for a square lattice \hspace {0.7in} b)
 The neighbors for a triangular lattice}

\end{figure}


\bigskip
\section{\bf Applying Colors}
\medskip

Each site of a spin model has a spin value at any time ranging from 0
to the number of states available minus one.  In our research the
number of states fell between two and four depending on what we
wanted to model.  Representing the various spins
is accomplished simply by using distinguishable colors to draw
the hexagonally shaped sites.  Important to following the performance
of a cluster update
algorithm, is the understanding of where and when bonds are placed
between sites, and in knowing the characteristics of the clusters
created during the updating procedures, such as the
sizes, shapes, and numbers.  Therefore the bonds are displayed as line
segments joining the center of the sites.  A cluster's
boundaries are displayed by highlighting its borders.  This involves
drawing lines between the sites of opposing clusters.  

\bigskip
\section{\bf Displaying the Various Updates}
\medskip

The various updates for the triangular lattice go about calculating
the new spins for the sites in quite a range of manors.  Therefore,
each update requires its own particular order of display function
calls.  All the updates can be shown with only three drawing
procedures.  These include drawing the hexagon
itself(XFillPolygon\cite[p. 185]{xviewprog}),
drawing a bond between the centers of two hexagons or
sites (XDrawLine\cite[p. 154]{xviewprog}), and last drawing a
border along the
edges of two  neighboring hexagons (XDrawLine\cite[p.
154]{xviewprog}).  For example, the
Metropolis update is quite simple and needs only to call 
the display procedure XFillPolygon, which displays a solid colored hexagon,
inside a loop in order to display the updated lattice. 

The Wolff update (figure 5) is a bit more complex than the Metropolis update.
Recall that the update picks a point and
creates bonds to some of its neighbors spreading from that site
outward  in all directions.  By displaying the bonds as they are
created, the user can visually grasp
exactly how the cluster (the group of sites connected by the bonds) is
created and what its shape and size are.  Afterwards, the lattice is
updated, but this requires only the sites in the newly formed cluster to be
redisplayed, for these are the only sites that change spins.    

More complex yet, is the Swendson-Wang
update (figure 6).  After all the bonds are calculated and the clusters are
labeled the graphics routines are called.  To begin, the bonds of the
largest cluster developed are drawn, since the largest
cluster is the most critical cluster to the update.  The clusters'
outlines are then
displayed to help the user distinguish which sites belong to which
clusters and to get an idea of the sizes and shapes of the clusters.
  Finally, the updating of the clusters is performed, which is
the exciting feature of
this update.  First the bonds are removed simply by redrawing the
lattice as before the update began and redrawing the cluster outlines.  These
together give the affect that the bonds are erased.  If we were to
update all the clusters at a time, it would be harder to follow exactly what
is happening, since there would be a sudden change in most of the spins.  In
order to prevent this, one tenth of all the clusters are updated
simultaneously.  The resulting affect to the eye, is that one by one
the sites in the clusters are being assigned a new spin value or new
color.  The screen becomes alive with activity during these few
seconds as the clusters are changing colors.  Throughout this display,
the cluster outlines are maintained by redrawing the boundaries over the
top of the newly drawn clusters.  To finish, the outlines are erased
and the lattice is back to a steady state ready to be
studied or updated again.

   The Plaquette update\cite {P}, specially designed for anti-ferromagnets, is
the fourth update included in this program.  In order to specify the
antiferromagnet model a negative beta value is entered.  
The previously mentioned updates
have been adapted for the anti-ferromagnet spin model (figure 7), but fail to produce
comparable results for the frustrated Ising model, since they produce
clusters which are too large or too small.  The Plaquette update utilizes the
same graphics
procedures as the Swendson-Wang update and has similar visual appeal.
The differences  between the two are that the Plaquette update only
works for the Ising model, the bonds are  calculated
differently and when the clusters are updated, instead of all the
sites being assigned the same new spin value during the updating they are
flipped to their opposite spin values.  

\bigskip
\section{\bf The Control Panel}
\medskip

   Important to using this program is the ease at which the user can
change the necessary parameters and control the updating of the
lattice.  For these necessities, a mouse oriented control panel (figure 4) is
used, created
using XView.  The panel has numerous slides, buttons, and input
locations to make controlling the program as simple as possible.  Three
choices include exiting(something we don't like to see), initializing
the lattice and saving the present lattice to a file.  On the panel
the user can select the initial state to create a new lattice with,
either {\it cold} - low temperature where all sites are set to
one spin,  {\it hot} - high temperature where spins are assigned
randomly, or {\it file} - load a
previously saved
lattice from a file. The dimensions of the lattice are
another parameter, including ranges of 4-128 for both x and y.  The
display window
is always the same size, so when the dimensions of the lattice are
changed the size of the hexagons and bonds are scaled proportionately.
Even the seed for the random number generator written for the program
is allocated space on the panel and can easily be varied.  

Once the lattice has been built the user can now experiment with it. 
The different updates each have their own button and when selected by the mouse
will engage and iterate one or more times depending on what the count slide is
set to at the bottom of the panel. 
Finally, and most importantly, the value Beta can be set on the panel.  This
allows the user direct interaction with the temperature of the spin model
and thus, control over how the updates will work.  The panel gives the user
control of the program in order to experiment with the lattice and the
updates to achieve the desired state while not being a hindrance.
    

\begin{figure}[htbp]

\vspace{3.5 in}

\caption{The control panel}

\end{figure}
  
\bigskip
\section{\bf Visualizing the Results}
\medskip

The advantages gained by this display program are easily recognizable.
The control panel makes the user environment powerful, yet friendly.
The user can easily understand
how the update works, how well it is working, and what status the
lattice is in by merely watching a window of the display.  This is
certainly much better than looking at numbers and trying to follow
what is taking place.

An additional advantage to the graphics representation of the spin
model is for developing update algorithms.  I found, when
working with the present updates, that it was much easier to find bugs
in the program by analyzing the displayed lattices than the code alone.
This benefit
carries over into finding problems in new updates we are working on
 developing.  Also, the many problems the current updates have can be
noticed readily when being viewed graphically and therefore, be
avoided in future update algorithms.  This tool will hopefully help us
find new update algorithms for triangular lattice spin models, in
particular the frustrated antiferromagnetic Ising Model.  It
serves as a stepping stone to developing better updates and
understanding the current updates more thoroughly.  

\bigskip
\section{\bf Current Research}
\medskip

Cluster algorithms can be generalized to other models.  However,
the main drawback of these methods is that 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.  Cluster algorithms do not work well for frustrated systems such as
spin glasses, which suffer the most severe critical slowing down.
These are models which have random frustration
(again frustration is where not all interacting spins can 
simultaneously have the lowest energy).

Some progress has been made, such as a Plaquette update for a square
lattice frustrated Ising model. 
We are trying to extend this method to other frustrated
systems. 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.

To aid us in continuing our research we are working on new displaying
techniques and features for spin model graphics.  In the near future, our
plans include 3-dimensional lattice graphics along with graphics for
algorithms running on the Connection Machine.  

\bigskip
\section{\bf Acknowledgments}
\medskip

Thanks is in order to the NSF for the grant that made this research project
possible, and Ofer Biham for organizing the REU program.  Dave Edelsohn
 deserves
much credit for writing the original XWindows graphics program for the
square lattice spin models.
Finally, our thanks goes out to everyone in the Computational Physics REU
program for their encouragement throughout and making this program a fun
and worthwhile experience.

\bigskip
\begin{thebibliography}{xviewprog}
 
\bibitem{potts}R.B. Potts, Proc. Camb. Phil. Soc. {\bf 48}, 106 (1952);
F.Y. Wu, Rev. Mod. Phys. {\bf 54}, 235 (1982).

\bibitem{ising}See for example B.~M.~ McCoy and T.~T.~Wu, {\em The Two-Dimensional Ising
Model,} (Harvard University Press, Cambridge, Mass., 1973).

\bibitem{monte}{\it Monte Carlo Methods in Statistical Physics, Topics in Current
Physics 7, Second Edition}, Ed. K. Binder (Springer-Verlag, Berlin, 1986);
{\it Applications of the Monte Carlo Method in Statistical Physics, Topics in
Current Physics 36, Second Edition}, Ed. K. Binder 
(Springer-Verlag, Berlin, 1987)

\bibitem{met}N. Metropolis {\it et al.}, J. Chem. Phys. {\bf 21}, 1087
(1953).

\bibitem{SW}R.H. Swendsen and J.-S. Wang, Phys. Rev. Lett. {\bf 58}, 86 (1987);
J.-S. Wang, R.H. Swendsen and R. Kotecky, Phys. Rev. Lett. {\bf 58}, 86 (1987).

\bibitem{W}U. Wolff, Phys. Rev. Lett. {\bf 62}, 361 (1989).

\bibitem{xviewprog}{\em Xlib Reference Manual Volume Two}, (O'Reilly and Associates Inc., Sebastopol, CA, 1990), pp. 154,185.

\bibitem{P}D. Kandel, R. Ben-Av and E. Domany, Phys. Rev. Lett. {\bf 65}, 941 (1990).

% \bibitem{Using C}Lee and Mark Atkinson, {\em Using C}, (QUE
% Corporation: Carmel, IN, 1990).

% \bibitem{latex}Leslie Lamport, {\em Latex}, (
% Addison-Wesley, Reading, MS, 1986).

\end{thebibliography}

\begin{figure}[htbp]

\vspace{9 in}

\caption{The Wolff update on a 40x40 triangular lattice}

\end{figure}

\begin{figure}[htbp]

\vspace{9 in}

\caption{The Swendson-Wang update on a 40x40 triangular lattice}

\end{figure}

\begin{figure}[htbp]

\vspace{9 in}

\caption{The frustrated antiferromagnet spin model on a 40x40 triangular lattice}

\end{figure}


\end{document}


From st8 Thu Aug  1 06:58:17 1991
Date: Thu, 1 Aug 91 06:58:16 EDT
From: st8 (Daniel Baumann)
Received: by sccs.syr.edu (4.1/1.0-6/5/90)
	id AA25558; Thu, 1 Aug 91 06:58:16 EDT
Message-Id: <9108011058.AA25558@sccs.syr.edu>
To: biham
Subject: The Paper
Status: RO

\documentstyle{article}
\bibliographystyle{plain}
\pagestyle{empty}
\pagenumbering{arabic}
\hoffset -2.5 cm
\textwidth 17 cm
\textheight 22 cm
\footskip 1 cm
\topmargin -1cm
\baselineskip 24pt
\begin{document}
                         \vspace*{0 cm}
 \begin{center}
 \huge\bf The Visualization of Triangular Lattice Spin Models \\
                         \vspace{2.5 cm}
 \Large\sc Daniel Baumann\\
                         \medskip
\large\sf Computational Physics Research Undergraduate, Syracuse University \\


                         \vspace{1.2 cm}

\Large \sc Paul Coddington \\
                         \medskip
 \large\sf Physics Department, Syracuse University, Syracuse, NY, 13244\\
\end{center}

                         \vspace{2 cm}

 \begin{abstract}
 \noindent\normalsize
To adequately understand spin models it is certainly helpful to use
computer graphics to visualize the models.  For the particular case of a
triangular  lattice, we developed
a fast and friendly program in the C language using Xwindows graphics
to help  us study and
create new Monte Carlo updating techniques that are essential to the
simulating of spin models.
Both cases of ferromagnets and anti-ferromagnets were adapted with the
Metropolis, Wolff, Swendson-Wang and Plaquette updates featured.  From
the usage of this program we hope to develop new and improved updating
procedures, and to better understanding the present update schemes.   
 \end{abstract}

                           \vfill
\newpage
\large
\section{\bf Spin Models of Magnets}
\medskip

Some materials can become magnetized due to complex interactions between
the spins of electrons in the atoms of the material. At high temperatures
there is a transition between a magnetized phase, where the spins
tend to be aligned (or ordered), and an unmagnetized phase where the spins
are disordered. Surprisingly, the behavior at this ``critical'' temperature 
is well described by very simple models of interacting spins on a lattice.

A simple spin model is the Potts model\cite {potts}, where the spin
can be in Q  
different states. For the ferromagnetic model, the interaction between
the spins is that if two
neighboring spins are in the same state, they have a smaller energy ($E = -1$) 
than if they are in different states (in which case $E = 0$). Hence the 
spins tend to align, except when the temperature becomes high enough so that
the thermal energy causes the system to become disordered. This is similar 
to how heating a solid (an ordered state) will cause it to melt into a liquid 
(a disordered state).  Opposite of the ferromagnet is the
antiferromagnet.  In this model the energy values are swapped and two
 neighboring spins will try to
oppose eachother's spins.  The two state triangular lattice has a geometry such
that not all interacting spins can be opposite simultaneously and therefore
have the lowest energy.  For this reason it is called a frustrated system.

\bigskip
\section{\bf Numerical Calculations}
\medskip

In the simplest case of only two states, this system is
 known as the Ising 
model\cite {ising}, and has been solved exactly in two dimensions,
greatly enhancing our 
understanding of magnetic systems, and phase transitions in general. More 
complicated models cannot be solved analytically, and in many cases the most
accurate results come from computer simulations.

A quantity such as the magnetization $M$ (which measures what proportion of
the spins are aligned), is calculated as follows : 
% the spins are aligned), is calculated by taking the thermodynamic average
% at a given temperature (here $\beta$ is the inverse temperature) :
$$
% <M> = {\sum_C M(C) e^{-\beta E(C)} \over \sum_C e^{-\beta E(C)} },
<M> = {1 \over Z} \sum_C M(C) e^{-\beta E(C)}, \qquad \quad Z = \sum_C e^{-\beta E(C)},
$$
% The sum is over
where $\beta$ is the inverse temperature, and the sum is over
all possible configurations $C$ of the spins on the lattice. $M(C)$ and
$E(C)$ are the magnetization and energy of a given configuration. For a 
$Q$-state Potts model on a lattice of $V$ sites, the number of possible
configurations of spins is $Q^V$, so summing over all configurations is
infeasible for all but the smallest lattices. 

\bigskip
\section{\bf Monte Carlo Simulations}
\medskip

Instead we use a
method known as ``Monte Carlo'' simulation\cite {monte} (since it is a stochastic, 
non-deterministic procedure, like spinning a roulette wheel) to generate the
configurations which make important contributions to the above sum.
% 
This is done by generating each configuration with a probability given by
its Boltzmann weight $e^{-\beta E} / Z$.
The standard way of generating these configurations is the Metropolis
algorithm, which works as follows :
\medskip
\begin{itemize}
  \item Propose a random change to one of the spins.
  \item If this decreases the energy, accept the change.
  \item If the energy is increased, accept the change with probability
                $e^{-\beta (E_{new} - E_{old})}$. 
\end{itemize}
\medskip
\noindent
This algorithm has very wide applicability, and is used not just for spin 
models, but in the simulation of a huge variety of systems.

Measurements of any quantity (such as the magnetization) can then be made on
these configurations, and the average over configurations taken. This will be
an approximation to the true value, with the usual statistical error, which 
is proportional to $1/\sqrt N$. Here $N$ is the number of {\it statistically
independent} (i.e. uncorrelated) configurations. 

\bigskip
\section{\bf A Problem --- Critical Slowing Down}
\medskip

For standard
update algorithms, such as Metropolis, the configurations are generally
correlated over many iterations, especially near a phase transition. This
is because these algorithms are {\it local} (i.e. the method depends only 
on the neighbors of the spin to be updated), whereas at the critical 
temperature the spins are correlated over large distances. In fact, as we 
increase our lattice size $L$, the number of iterations needed to generate 
an independent configuration grows roughly as $L^2$, so the calculation
quickly becomes computationally intractable.
This is known as critical slowing down, and is a major problem for Monte 
Carlo simulations.

\bigskip
\section{\bf A Solution --- Cluster Algorithms}
\medskip

A non-local updating scheme which can dramatically reduce critical slowing
down has recently been introduced by Swendsen and Wang\cite {SW}.
Their algorithm  is
very simple -- if two neighboring spins are the same, a bond is placed 
between them with probability $1-e^{-\beta}$. This creates clusters of bonded
spins, and all the spins in a cluster can be changed to a value 
chosen at random for each cluster. A variation of this algorithm, due to 
Wolff\cite {W}, is to pick a site at random and generate a single cluster around it.
This will tend to produce larger clusters, and decorrelate the configurations
even faster.  For the same computational cost, the Metropolis algorithm 
changes the configuration only slightly, leaving the large scale structure 
intact, whereas the cluster algorithms both produce a completely different
configuration. 



\bigskip
\section{\bf Displaying Spin Models on Computers}
\medskip

By visualizing spin models we can better understand cluster
algorithms, and gain insight into new algorithms. Since computers are necessary
to perform simulations of spin models it is only natural to
utilize their graphics capabilities.  This is especially true when high-powered
workstations are available like the Sun Sparc Stations. XWindows was chosen
 for the graphics due to its portability, quickness and
high resolution.

For 2-dimensional lattice spin models, the sites can be mapped onto
the display with little effort and the scaling parameters added to
zoom inward and outward.  3-dimensional lattices are another case.
To adequately display them interactively would probably  require the
use of powerful Silicon Graphics Workstations creating translucensy and
three-dimensional images.  During this particular research project we
focused on the 2-dimensional lattices, in particular the triangular
lattice. 


\bigskip
\section{\bf The Triangular Lattice}
\medskip

To visualize spin models it is necessary to show what state or spin value
the different sites have for the particular lattice involved.  The sites are
located at the intersections in the lattice.  For example, a square
lattice has regularly spaced sites in rows and columns.  To see this,
imagine a screen on your window at home and wherever the wires
cross a site exists.  This is a bit more complicated when trying to
grasp a triangular lattice.

The sites for a triangular lattice spin model are located at the
intersections of a triangular grid (figure 1a), however the representation
 of the sites themselves are
not triangular, but hexagonal as figure 1b shows.  Each hexagon
represents one site in the model and is filled solid with a color depending on
its particular spin.  The result is that a triangular lattice appears
to be a grid of hexagons,  while the bonds between sites form the
triangular pattern one would expect to see (figure 1c).



\begin{figure}[h]

\vspace{3 in}

\caption{a) triangular grid \hspace {.5in} b) hexagonal grid of sites
\hspace {.5in} c) the sites on the grid}

\end{figure}




\medskip
\subsection{\bf A Rectangular Shaped Triangular Lattice}
\medskip    

It is convenient to display the triangular lattice such that the
overall shape is a rectangle.  In addition, rectangular arrays are convenient
for storing the values of the spins.  For this
particular project, the rectangle's dimensions ranged from 4x4 up to 128x128 sites.
Mapping the values of the sites in the array to the displayed
honeycomb of hexagons is a task all in itself.  It was decided
that the first column of the array would start in the upper left-hand
corner of the window and each column to its right would be shifted
down half the height of a hexagon.  The result is a grid of hexagons
whose top boundary slopes downward from left to right.  To fix this
slope, the hexagons cut off at the bottom of the window are
drawn at the top.  This accurately represents the system because the
rectangle is designed to be a torus in which case the bottom hexagons wrap
around to the top.  Likewise, the hexagons on the right wrap around to
the left.  Not only are the hexagons displayed as a torus, but
the communication between sites behaves in the same fashion.  To
further add to the torus effect, the bottom hexagons in the even
columns of the rectangle, which protrude below the bottom of the window, are cut in
half and drawn at the top of the display.  The same goes for the
hexagons in the right most column, who have a portion of them
displayed on the left.  Care must be taken in this case, however,
because if there are an odd number of columns the cut and pasting
does not have the desired affect and creates troublesome overlap.  Lastly, the
hexagon in the bottom right
corner is cut in two directions, and thus, into four pieces (figure 2).     

\begin{figure}[h]

\vspace{4.0 in}

\caption{A triangular lattice in a rectangular window}

\end{figure}

\medskip
\subsection{\bf Neighbors}
\medskip

The theory behind spin models is that the sites affect one another
depending on whether the spin values are similar or different.
Thus, to update a site or create bonds between a site and its neighbor it is
necessary to know what spins its neighbors have in relation to its
own.  For spin
models only the interactions with the nearest neighbors of a site are
necessary since the
influence of more distant sites is relatively non-existent.  Who a site's
closest neighbors are depends on what type of lattice the site is in.
For a square lattice the neighbors for the (i,j) site are {(i+1,j), 
(i-1,j), (i,j+1), (i,j-1)} (figure 3a).  The diagonal neighbors are
not influential enough to include.  On a triangular lattice, each site
has six neighbors.  These include the same four neighbors as above,
but also (i+1,j-1) and (i-1,j+1) (figure 3b).

\begin{figure}[h]

\vspace{2.4 in}

\caption{a) The neighbors for a square lattice \hspace {0.7in} b)
 The neighbors for a triangular lattice}

\end{figure}


\bigskip
\section{\bf Applying Colors}
\medskip

Each site of a spin model has a spin value at any time ranging from 0
to the number of states available minus one.  In our research the
number of states fell between two and four depending on what we
wanted to model.  Representing the various spins
is accomplished simply by using distinguishable colors to draw
the hexagonally shaped sites.  Important to following the performance
of a cluster update
algorithm, is the understanding of where and when bonds are placed
between sites, and in knowing the characteristics of the clusters
created during the updating procedures, such as the
sizes, shapes, and numbers.  Therefore the bonds are displayed as line
segments joining the center of the sites.  A cluster's
boundaries are displayed by highlighting its borders.  This involves
drawing lines between the sites of opposing clusters.  

\bigskip
\section{\bf Displaying the Various Updates}
\medskip

The various updates for the triangular lattice go about calculating
the new spins for the sites in quite a range of manors.  Therefore,
each update requires its own particular order of display function
calls.  All the updates can be shown with only three drawing
procedures.  These include drawing the hexagon
itself(XFillPolygon\cite[p. 185]{xviewprog}),
drawing a bond between the centers of two hexagons or
sites (XDrawLine\cite[p. 154]{xviewprog}), and last drawing a
border along the
edges of two  neighboring hexagons (XDrawLine\cite[p.
154]{xviewprog}).  For example, the
Metropolis update is quite simple and needs only to call 
the display procedure XFillPolygon, which displays a solid colored hexagon,
inside a loop in order to display the updated lattice. 

The Wolff update (figure 5) is a bit more complex than the Metropolis update.
Recall that the update picks a point and
creates bonds to some of its neighbors spreading from that site
outward  in all directions.  By displaying the bonds as they are
created, the user can visually grasp
exactly how the cluster (the group of sites connected by the bonds) is
created and what its shape and size are.  Afterwards, the lattice is
updated, but this requires only the sites in the newly formed cluster to be
redisplayed, for these are the only sites that change spins.    

More complex yet, is the Swendson-Wang
update (figure 6).  After all the bonds are calculated and the clusters are
labeled the graphics routines are called.  To begin, the bonds of the
largest cluster developed are drawn, since the largest
cluster is the most critical cluster to the update.  The clusters'
outlines are then
displayed to help the user distinguish which sites belong to which
clusters and to get an idea of the sizes and shapes of the clusters.
  Finally, the updating of the clusters is performed, which is
the exciting feature of
this update.  First the bonds are removed simply by redrawing the
lattice as before the update began and redrawing the cluster outlines.  These
together give the affect that the bonds are erased.  If we were to
update all the clusters at a time, it would be harder to follow exactly what
is happening, since there would be a sudden change in most of the spins.  In
order to prevent this, one tenth of all the clusters are updated
simultaneously.  The resulting affect to the eye, is that one by one
the sites in the clusters are being assigned a new spin value or new
color.  The screen becomes alive with activity during these few
seconds as the clusters are changing colors.  Throughout this display,
the cluster outlines are maintained by redrawing the boundaries over the
top of the newly drawn clusters.  To finish, the outlines are erased
and the lattice is back to a steady state ready to be
studied or updated again.

   The Plaquette update\cite {P}, specially designed for anti-ferromagnets, is
the fourth update included in this program.  In order to specify the
antiferromagnet model a negative beta value is entered.  
The previously mentioned updates
have been adapted for the anti-ferromagnet spin model (figure 7), but fail to produce
comparable results for the frustrated Ising model, since they produce
clusters which are too large or too small.  The Plaquette update utilizes the
same graphics
procedures as the Swendson-Wang update and has similar visual appeal.
The differences  between the two are that the Plaquette update only
works for the Ising model, the bonds are  calculated
differently and when the clusters are updated, instead of all the
sites being assigned the same new spin value during the updating they are
flipped to their opposite spin values.  

\bigskip
\section{\bf The Control Panel}
\medskip

   Important to using this program is the ease at which the user can
change the necessary parameters and control the updating of the
lattice.  For these necessities, a mouse oriented control panel (figure 4) is
used, created
using XView.  The panel has numerous slides, buttons, and input
locations to make controlling the program as simple as possible.  Three
choices include exiting(something we don't like to see), initializing
the lattice and saving the present lattice to a file.  On the panel
the user can select the initial state to create a new lattice with,
either {\it cold} - low temperature where all sites are set to
one spin,  {\it hot} - high temperature where spins are assigned
randomly, or {\it file} - load a
previously saved
lattice from a file. The dimensions of the lattice are
another parameter, including ranges of 4-128 for both x and y.  The
display window
is always the same size, so when the dimensions of the lattice are
changed the size of the hexagons and bonds are scaled proportionately.
Even the seed for the random number generator written for the program
is allocated space on the panel and can easily be varied.  

Once the lattice has been built the user can now experiment with it. 
The different updates each have their own button and when selected by the mouse
will engage and iterate one or more times depending on what the count slide is
set to at the bottom of the panel. 
Finally, and most importantly, the value Beta can be set on the panel.  This
allows the user direct interaction with the temperature of the spin model
and thus, control over how the updates will work.  The panel gives the user
control of the program in order to experiment with the lattice and the
updates to achieve the desired state while not being a hindrance.
    

\begin{figure}[htbp]

\vspace{3.5 in}

\caption{The control panel}

\end{figure}
  
\bigskip
\section{\bf Visualizing the Results}
\medskip

The advantages gained by this display program are easily recognizable.
The control panel makes the user environment powerful, yet friendly.
The user can easily understand
how the update works, how well it is working, and what status the
lattice is in by merely watching a window of the display.  This is
certainly much better than looking at numbers and trying to follow
what is taking place.

An additional advantage to the graphics representation of the spin
model is for developing update algorithms.  I found, when
working with the present updates, that it was much easier to find bugs
in the program by analyzing the displayed lattices than the code alone.
This benefit
carries over into finding problems in new updates we are working on
 developing.  Also, the many problems the current updates have can be
noticed readily when being viewed graphically and therefore, be
avoided in future update algorithms.  This tool will hopefully help us
find new update algorithms for triangular lattice spin models, in
particular the frustrated antiferromagnetic Ising Model.  It
serves as a stepping stone to developing better updates and
understanding the current updates more thoroughly.  

\bigskip
\section{\bf Current Research}
\medskip

Cluster algorithms can be generalized to other models.  However,
the main drawback of these methods is that 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.  Cluster algorithms do not work well for frustrated systems such as
spin glasses, which suffer the most severe critical slowing down.
These are models which have random frustration
(again frustration is where not all interacting spins can 
simultaneously have the lowest energy).

Some progress has been made, such as a Plaquette update for a square
lattice frustrated Ising model. 
We are trying to extend this method to other frustrated
systems. 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.

To aid us in continuing our research we are working on new displaying
techniques and features for spin model graphics.  In the near future, our
plans include 3-dimensional lattice graphics along with graphics for
algorithms running on the Connection Machine.  

\bigskip
\section{\bf Acknowledgments}
\medskip

Thanks is in order to the NSF for the grant that made this research project
possible, and Ofer Biham for organizing the REU program.  Dave Edelsohn
 deserves
much credit for writing the original XWindows graphics program for the
square lattice spin models.
Finally, our thanks goes out to everyone in the Computational Physics REU
program for their encouragement throughout and making this program a fun
and worthwhile experience.

\bigskip
\begin{thebibliography}{xviewprog}

\bibitem{Using C}Atkinson, Lee and Mark, {\em Using C}. Carmel, IN: QUE
Corporation, 1990.

\bibitem{latex}Lamport, Leslie, {\em Latex}. Reading, Mass.:
Addison-Wesley Publishing Company, 1986.

\bibitem{xviewprog}{\em Xlib Reference Manual Volume Two}. Sebastopol,
CA: O'Reilly and Associates Inc., 1990.



\bibitem{SW}R.H. Swendsen and J.-S. Wang, Phys. Rev. Lett. {\bf 58}, 86 (1987);
J.-S. Wang, R.H. Swendsen and R. Kotecky, Phys. Rev. Lett. {\bf 58}, 86 (1987).



\bibitem{W}U. Wolff, Phys. Rev. Lett. {\bf 62}, 361 (1989).



\bibitem{P}D. Kandel, R. Ben-Av and E. Domany, Phys. Rev. Lett. {\bf 65}, 941 (1990).


 
\bibitem{potts}R.B. Potts, Proc. Camb. Phil. Soc. {\bf 48}, 106 (1952);
F.Y. Wu, Rev. Mod. Phys. {\bf 54}, 235 (1982)


\bibitem{ising}See for example B.~M.~ McCoy and T.~T.~Wu, {\em The Two-Dimensional Ising
Model,} (Harvard University Press, Cambridge, Mass., 1973).



\bibitem{monte}{\it Monte Carlo Methods in Statistical Physics, Topics in Current
Physics 7, Second Edition}, Ed. K. Binder (Springer-Verlag, Berlin, 1986);
{\it Applications of the Monte Carlo Method in Statistical Physics, Topics in
Current Physics 36, Second Edition}, Ed. K. Binder 
(Springer-Verlag, Berlin, 1987)



\end{thebibliography}

\begin{figure}[htbp]

\vspace{9 in}

\caption{The Wolff update on a 40x40 triangular lattice}

\end{figure}

\begin{figure}[htbp]

\vspace{9 in}

\caption{The Swendson-Wang update on a 40x40 triangular lattice}

\end{figure}

\begin{figure}[htbp]

\vspace{9 in}

\caption{The frustrated antiferromagnet spin model on a 40x40 triangular lattice}

\end{figure}


\end{document}



