Swendsen–Wang Algorithm
   HOME

TheInfoList



OR:

The Swendsen–Wang algorithm is the first non-local or cluster
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
for
Monte Carlo simulation Monte Carlo methods, or Monte Carlo experiments, are a broad class of computational algorithms that rely on repeated random sampling to obtain numerical results. The underlying concept is to use randomness to solve problems that might be determ ...
for large systems near criticality. It has been introduced by
Robert Swendsen Robert Haakon Swendsen is Professor of Physics at Carnegie Mellon University. He is known in the computational physics community for the Swendsen-Wang algorithm, the Monte Carlo Renormalization Group and related methods that enable efficient com ...
and Jian-Sheng Wang in 1987 at
Carnegie Mellon Carnegie may refer to: People * Carnegie (surname), including a list of people with the name * Clan Carnegie, a lowland Scottish clan Institutions Named for Andrew Carnegie *Carnegie Building (Troy, New York), on the campus of Rensselaer Polyt ...
. The original algorithm was designed for the
Ising Ising is a surname. Notable people with the surname include: * Ernst Ising (1900–1998), German physicist * Gustav Ising (1883–1960), Swedish accelerator physicist * Rudolf Ising, animator for ''MGM'', together with Hugh Harman often credited ...
and Potts models, and it was later generalized to other systems as well, such as the XY model by
Wolff algorithm The Wolff algorithm, named after Ulli Wolff, is an algorithm for Monte Carlo simulation of the Ising model and Potts model in which the unit to be flipped is not a single spin (as in the heat bath or Metropolis algorithms) but a cluster of the ...
and particles of fluids. The key ingredient was the
random cluster model In statistical mechanics, probability theory, graph theory, etc. the random cluster model is a random graph that generalizes and unifies the Ising model, Potts model, and percolation model. It is used to study random combinatorial structures, elec ...
, a representation of the Ising or
Potts Potts may refer to: Arts and entertainment *Doc Potts, animated television series * Tom Potts, Child ballad 109 *The Potts, said to be the world's longest-running cartoon strip drawn by the same artist Mathematics *Potts model, model of interact ...
model through percolation models of connecting bonds, due to Fortuin and Kasteleyn. It has been generalized by Barbu and Zhu to arbitrary sampling probabilities by viewing it as a
Metropolis–Hastings algorithm In statistics and statistical physics, the Metropolis–Hastings algorithm is a Markov chain Monte Carlo (MCMC) method for obtaining a sequence of random samples from a probability distribution from which direct sampling is difficult. This seq ...
and computing the acceptance probability of the proposed Monte Carlo move.


Motivation

The problem of the critical slowing-down affecting local processes is of fundamental importance in the study of second-order
phase transition In chemistry, thermodynamics, and other related fields, a phase transition (or phase change) is the physical process of transition between one state of a medium and another. Commonly the term is used to refer to changes among the basic states ...
s (like ferromagnetic transition in the
Ising model The Ising model () (or Lenz-Ising model or Ising-Lenz model), named after the physicists Ernst Ising and Wilhelm Lenz, is a mathematical model of ferromagnetism in statistical mechanics. The model consists of discrete variables that represent ...
), as increasing the size of the system in order to reduce finite-size effects has the disadvantage of requiring a far larger number of moves to reach thermal equilibrium. Indeed the correlation time \tau usually increases as L^z with z\simeq 2 or greater; since, to be accurate, the simulation time must be t\gg\tau, this is a major limitation in the size of the systems that can be studied through local algorithms. SW algorithm was the first to produce unusually small values for the dynamical critical exponents: z=0.35 for the 2D Ising model (z=2.125 for standard simulations); z=0.75 for the 3D Ising model, as opposed to z=2.0 for standard simulations.


Description

The algorithm is non-local in the sense that a single sweep updates a collection of spin variables based on the Fortuin–Kasteleyn representation. The update is done on a "cluster" of spin variables connected by open bond variables that are generated through a
percolation Percolation (from Latin ''percolare'', "to filter" or "trickle through"), in physics, chemistry and materials science, refers to the movement and filtering of fluids through porous materials. It is described by Darcy's law. Broader applicatio ...
process, based on the interaction states of the spins. Consider a typical ferromagnetic Ising model with only nearest-neighbor interaction. * Starting from a given configuration of spins, we associate to each pair of nearest neighbours on sites n,m a random variable b_\in \lbrace 0,1\rbrace which is interpreted in the following way: if b_=0 then there is no link between the sites n and m (the bond is closed); if b_=1 then there is a link connecting the spins \sigma_n \text \sigma_m(the bond is open). These values are assigned according to the following (conditional) probability distribution: P\left \sigma_n\neq\sigma_m\right1; P\left \sigma_n\neq\sigma_m\right0; P\left \sigma_n=\sigma_m\righte^; P\left \sigma_n=\sigma_m\right1-e^; where J_>0 is the ferromagnetic coupling strength. This probability distribution has been derived in the following way: the Hamiltonian of the Ising model is H
sigma Sigma (; uppercase Σ, lowercase σ, lowercase in word-final position ς; grc-gre, σίγμα) is the eighteenth letter of the Greek alphabet. In the system of Greek numerals, it has a value of 200. In general mathematics, uppercase Σ is used ...
\sum\limits_-J_\sigma_i\sigma_j, and the partition function is Z=\sum\limits_e^. Consider the interaction between a pair of selected sites n and m and eliminate it from the total Hamiltonian, defining H_
sigma Sigma (; uppercase Σ, lowercase σ, lowercase in word-final position ς; grc-gre, σίγμα) is the eighteenth letter of the Greek alphabet. In the system of Greek numerals, it has a value of 200. In general mathematics, uppercase Σ is used ...
\sum\limits_-J_\sigma_i\sigma_j. Define also the restricted sums: Z_^=\sum\limits_e^\delta_; Z_^=\sum\limits_e^\left(1-\delta_\right). Z=e^Z_^+e^Z_^. Introduce the quantity Z_^=Z_^+Z_^; the partition function can be rewritten as Z=\left(e^-e^\right)Z_^+e^Z_^. Since the first term contains a restriction on the spin values whereas there is no restriction in the second term, the weighting factors (properly normalized) can be interpreted as probabilities of forming/not forming a link between the sites: P_=1-e^. The process can be easily adapted to antiferromagnetic spin systems, as it is sufficient to eliminate Z_^ in favor of Z_^ (as suggested by the change of sign in the interaction constant). * After assigning the bond variables, we identify the same-spin clusters formed by connected sites and make an inversion of all the variables in the cluster with probability 1/2. At the following time step we have a new starting Ising configuration, which will produce a new clustering and a new collective spin-flip.


Correctness

It can be shown that this algorithm leads to equilibrium configurations. To show this, we interpret the algorithm as a
Markov chain A Markov chain or Markov process is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally, this may be thought of as, "What happen ...
, and show that the chain is both
ergodic In mathematics, ergodicity expresses the idea that a point of a moving system, either a dynamical system or a stochastic process, will eventually visit all parts of the space that the system moves in, in a uniform and random sense. This implies t ...
(when used together with other algorithms) and satisfies
detailed balance The principle of detailed balance can be used in kinetic systems which are decomposed into elementary processes (collisions, or steps, or elementary reactions). It states that at equilibrium, each elementary process is in equilibrium with its reve ...
, such that the equilibrium
Boltzmann distribution In statistical mechanics and mathematics, a Boltzmann distribution (also called Gibbs distribution Translated by J.B. Sykes and M.J. Kearsley. See section 28) is a probability distribution or probability measure that gives the probability ...
is equal to the
stationary distribution Stationary distribution may refer to: * A special distribution for a Markov chain such that if the chain starts with its stationary distribution, the marginal distribution of all states at any time will always be the stationary distribution. Assum ...
of the chain. Ergodicity means that it is possible to transit from any initial state to any final state with a finite number of updates. It has been shown that the SW algorithm is not ergodic in general (in the thermodynamic limit). Thus in practice, the SW algorithm is usually used in conjunction with single spin-flip algorithms such as the Metropolis–Hastings algorithm to achieve ergodicity. The SW algorithm does however satisfy detailed-balance. To show this, we note that every transition between two Ising spin states must pass through some bond configuration in the percolation representation. Let's fix a particular bond configuration: what matters in comparing the probabilities related to it is the number of factors q=e^ for each missing bond between neighboring spins with the same value; the probability of going to a certain Ising configuration compatible with a given bond configuration is uniform (say p). So the ratio of the transition probabilities of going from one state to another is \frac=\frac=\frac =e^ since \Delta E=-\sum\limits_J_\left(\sigma'_l \sigma'_m - \sigma_l \sigma_m\right)=-\sum\limits_J_\left delta_-\left(1-\delta_\right)-\delta_+\left(1-\delta_\right)\right-2\sum\limits_J_\left(\delta_-\delta_\right). This is valid for every bond configuration the system can pass through during its evolution, so detailed balance is satisfied for the total transition probability. This proves that the algorithm is correct.


Efficiency

Although not analytically clear from the original paper, the reason why all the values of z obtained with the SW algorithm are much lower than the exact lower bound for single-spin-flip algorithms (z\geq\gamma/\nu) is that the correlation length divergence is strictly related to the formation of percolation clusters, which are flipped together. In this way the relaxation time is significantly reduced. Another way to view this is through the correspondence between the spin statistics and cluster statistics in the Edwards-Sokal representation.


Generalizations

The algorithm is not efficient in simulating frustrated systems, because the correlation length of the clusters is larger than the correlation length of the spin model in the presence of frustrated interactions. Currently, there are two main approaches to addressing this problem, such that the efficiency of cluster algorithms is extended to frustrated systems. The first approach is to extend the bond-formation rules to more non-local cells, and the second approach is to generate clusters based on more relevant order parameters. In the first case, we have the
KBD algorithm The KBD algorithm is a cluster update algorithm designed for the fully frustrated Ising model in two dimensions, or more generally any two dimensional spin glass with frustrated plaquettes arranged in a checkered pattern. It is discovered in 1 ...
for the fully-frustrated Ising model, where the decision of opening bonds are made on each plaquette, arranged in a checkerboard pattern on the square lattice. In the second case, we have
replica cluster move Replica cluster move in condensed matter physics refers to a family of non-local cluster algorithms used to simulate spin glasses. It is an extension of the Swendsen-Wang algorithm in that it generates non-trivial spin clusters informed by the inte ...
for low-dimensional
spin glasses In condensed matter physics, a spin glass is a magnetic state characterized by randomness, besides cooperative behavior in freezing of spins at a temperature called 'freezing temperature' ''Tf''. In ferromagnetic solids, component atoms' magne ...
, where the clusters are generated based on spin overlaps, which is believed to be the relevant order parameter.


See also

*
Random cluster model In statistical mechanics, probability theory, graph theory, etc. the random cluster model is a random graph that generalizes and unifies the Ising model, Potts model, and percolation model. It is used to study random combinatorial structures, elec ...
*
Monte Carlo method Monte Carlo methods, or Monte Carlo experiments, are a broad class of computational algorithms that rely on repeated random sampling to obtain numerical results. The underlying concept is to use randomness to solve problems that might be deter ...
*
Wolff algorithm The Wolff algorithm, named after Ulli Wolff, is an algorithm for Monte Carlo simulation of the Ising model and Potts model in which the unit to be flipped is not a single spin (as in the heat bath or Metropolis algorithms) but a cluster of the ...
* http://www.hpjava.org/theses/shko/thesis_paper/node69.html *http://www-fcs.acs.i.kyoto-u.ac.jp/~harada/monte-en.html


References

* *Kasteleyn P. W. and Fortuin (1969) J. Phys. Soc. Jpn. Suppl. 26s:11 * * * {{DEFAULTSORT:Swendsen-Wang algorithm Monte Carlo methods Statistical mechanics Critical phenomena Phase transitions