The goal of computer simulations of spin models is
to generate configurations of spins typical of statistical equilibrium
and measure physical observables on this ensemble of configurations.
The generation of configurations is traditionally performed by Monte
Carlo methods such as the
Metropolis algorithm [Metropolis:53a], which
produce configurations with a probability given by the Boltzmann
distribution , where
is the action, or
energy, of the system in configuration
, and
is the
inverse temperature. One of the main problems with these methods in
practice is that successive configurations are not statistically
independent, but rather are correlated with some autocorrelation time,
, between effectively independent configurations.
A key feature of traditional (Metropolislike) Monte Carlo algorithms is
that the updates are local (i.e., one spin at a time is updated), and
its new value depends only on the values of spins which affect its
contribution to the action, that is, only on local (usually nearest
neighbor) spins. Thus, in a single step of the algorithm, information about
the state of a spin is transmitted only to its nearest neighbors. In order
for the system to reach a new effectively independent configuration, this
information must travel a distance of order the (static or spatial)
correlation length . As the information
executes a random walk around the lattice, one would suppose that the
autocorrelation time
. However, in general,
, where z is called the dynamical critical exponent.
Almost all numerical simulations of spin models have measured
for local update algorithms. (See also Sections 4.3,
4.4, 7.3, 12.6, and 14.2).
For a spin model with a phase transition, as
the inverse temperature approaches the critical value,
diverges to infinity so that the computational efficiency rapidly goes
to zero! This behavior is called critical slowing down (CSD),
and until very recently it has plagued Monte Carlo simulations of
statistical mechanical systems, in particular spin models, at or near
their phase transitions. Recently, however, several new ``cluster
algorithms'' have been introduced which decrease z dramatically by
performing nonlocal spin updates, thus reducing (or even
eliminating) CSD and facilitating much more efficient computer
simulations.