Editing Cluster algorithms

Jump to navigation Jump to search
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.

The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then publish the changes below to finish undoing the edit.

Latest revision Your text
Line 1: Line 1:
'''Cluster algorithms''' are mainly used in the simulation of [[Ising Models|Ising-like models]] using [[Monte Carlo|Monte Carlo]] methods. The essential feature is the use of collective motions of particles (spins) in a single [[Monte Carlo]] step.
'''Cluster algorithms''' are mainly used in the simulation of [[Ising Models|Ising-like models]]. The essential feature is the use of collective motions
An interesting property of some of these applications is the fact that the [[percolation analysis]] of the clusters can
of ''particles (spins)'' in a single Monte Carlo step.
be used to study [[phase transitions]].
An interesting property of some of these application is the fact that the [[percolation analysis]] of the clusters can
be used to study phase transitions.
== Swendsen-Wang algorithm ==
== Swendsen-Wang algorithm ==
As an introductory example to the Swendsen-Wang algorithm we shall discuss the technique
As an introductory example we shall discuss the Swendsen-Wang technique (Ref 1) in the simulation of [[Ising Models]].
<ref>[http://dx.doi.org/10.1103/PhysRevLett.58.86  Robert H. Swendsen and Jian-Sheng Wang, "Nonuniversal critical dynamics in Monte Carlo simulations", Physical Review Letters '''58''' pp. 86-88 (1987)] </ref>
=== Recipe ===
in the simulation of the
In one [[Monte Carlo]] step of the algorithm the following recipe is used:
[[Ising Models |Ising model]]. In one [[Monte Carlo]] step of the algorithm the following recipe is used:


# Consider every pair of interacting sites (spins). In the current configuration the [[Intermolecular pair potential |pair interaction]] can be either negative: <math> \Phi_{ij}/k_B T= -K  </math> or positive <math> \Phi_{ij}/k_B T = + K </math>, depending on the product: <math> S_{i} S_{j} </math> (See the [[Ising Models |Ising model]] entry for notation).
* Consider every pair interacting sites (spins)
#For pairs of interacting sites (i.e. nearest neighbours) with <math> \Phi_{ij}/k_B T < 0 </math>, [[random numbers |randomly]] create a bond between the two spins with a given probability <math> p </math>, where <math> p </math> will be chosen to be a function of <math> K </math>.
 
#The bonds generated in the previous step are used to build up clusters of sites (spins).
In the current configuration the [[Intermolecular pair potential |pair interaction]] can be either negative: <math> \Phi_{ij}/k_B T= -K  </math> or positive <math> \Phi_{ij}/k_B T = + K </math>,  
#Build up the partition of the system in the corresponding clusters of spins. In each cluster all the spins will have the same state, either <math> S = 1 </math> or <math> S = -1 </math>.
depending on the product: <math> S_{i} S_{j} </math> (See [[Ising Models]] for details on the notation)
#For each cluster, independently, choose at random with equal probabilities whether or not to flip (invert the value of <math> S </math>) the whole set of spins belonging to the cluster. The bonding probability <math> p </math> is given by: <math> p = 1 - \exp [ -2 K ] </math>.
 
* For pairs of interacting sites (nearest neighbors) with <math> \Phi_{ij}/k_B T < 0 </math> create a bond between the two spins with a given probability <math> p </math> (using [[random numbers]])
 
: <math> p </math> will be chosen to be a function of <math> K </math>  
* The bonds generated in the previous step are used to build up clusters of sites (spins).
 
* Build up the partition of the system in the corresponding clusters of spins.
 
In each cluster all the spins will have the same state (either <math> S = 1 </math> or <math> S = -1 </math>)
 
* For each cluster, independently, choose at random with equal probabilities whether to flip (invert the value of <math> S </math>) or not to flip the whole set of spins belonging to the cluster.
 
 
The bonding probability <math> p </math> is given by:
 
: <math> p = 1 - \exp [ -2 K ] </math>


== Wolff algorithm ==
== Wolff algorithm ==
See Ref 2 for details.
The procedure to create a given bond is the same as in the Swendsen-Wang algorithm. However in Wolff's method
The procedure to create a given bond is the same as in the Swendsen-Wang algorithm. However in Wolff's method
the whole set of interacting pairs is not tested to generate (possible) bonds. Instead, a single cluster
the whole set of interacting pairs is not tested to generate (possible) bonds. In stead, a single cluster
is built. See
is built.  
<ref>[http://dx.doi.org/10.1103/PhysRevLett.62.361 Ulli Wolff, "Collective Monte Carlo Updating for Spin Systems" , Physical Review Letters '''62''' pp. 361-364 (1989)]</ref>
 
for details.  
* The initial cluster contains one site (selected at random)
 
* Possible bonds between the initial site and  other sites of the system are tested:
 
The bonded sites are included in the cluster
 
* Then recursively, one checks the existence of bonds between the new members of the cluster and sites of the system to add, if bonds are generated, new sites to the ''growing'' cluster, until no more bonds are generated.


#The initial cluster contains one site, which is selected at random.
* At this point, the whole cluster is flipped (see above)
#Possible bonds between the initial site and  other sites of the system are tested. Bonded sites are included in the cluster.
#Recursively, one checks the existence of bonds between the new members of the cluster and sites of the system to add, if bonds are generated,  new sites to the ''growing'' cluster, until no more bonds are generated.
#At this point, the whole cluster is flipped (see above).


== Invaded Cluster Algorithm ==
== Invaded Cluster Algorithm ==
The purpose of this algorithm is to locate [[critical points]] (i.e. the critical temperature). So, in this case
(See Ref 3)
the probability of bonding neighbouring sites with equal spins is not set ''a priori'' (See
 
<ref>[http://dx.doi.org/10.1103/PhysRevLett.75.2792    J. Machta, Y. S. Choi, A. Lucke,  T. Schweizer, and L. V. Chayes, "Invaded Cluster Algorithm for Equilibrium Critical Points", Physical Review Letters '''75''' pp. 2792-2795 (1995)]</ref>).
The purpose of this algorithm is to locate [[critical points]] (critical temperature). So, in this case
the probability of bonding neighboring sites with equal spins is not set ''a priori''.
 
The algorithm for an Ising system with [[periodic boundary conditions]] can be implemented as follows:
The algorithm for an Ising system with [[periodic boundary conditions]] can be implemented as follows:


Given a certain configuration of the system:
Given a certain configuration of the system:


#One considers the possible bonds in the system (pairs of nearest neighbours with favourable interaction).
* We consider the possible bonds on the system (pairs of nearest neighbours with favourable interaction)
#One assigns a [[random numbers |random]]  order to these possible bonds.
 
#The possible bonds are ''activated''  in the order fixed in the previous step (the cluster structure is watched during this process).
* Using [[random numbers]] we asign a random order to these possible bonds
#The bond activation stops when one cluster percolates through the entire system (i.e. considering the periodic boundary conditions the cluster becomes of infinite size).
 
#Every cluster is then is flipped with  probability 1/2, as in the Swendsen-Wang algorithm.
* The possible bonds are being ''activated''  in the order fixed in the previous step (the cluster structure is watched during this process)
#An effective bond probability for the percolation threshold, <math> p_{per} </math> can be computed as <math> p_{per} = M_{act}/M </math> with <math> M_{act}</math> being the number of activated bonds when the first cluster percolates, and <math> M </math> is the number of possible bonds.
 
#The value of <math> p_{per} </math> (in one realisation, or the averaged value over the simulation, see  references for a practical application) can be related with the critical coupling constant, <math> k_c </math> as <math> p_{per} \approx  1 - \exp \left[ - 2 k_c \right]  </math>.
* The bond activation stops when one cluster percolates through the entire system (i.e. considering the periodic boundary conditions
the cluster becomes of inifinite size)
 
* Then,  every cluster (as in the Swendsen-Wang algorithm) is flipped with proability 1/2.
 
* An effective bond probability for the percolation threshold, <math> p_{per} </math> can be computed as:
 
: <math> p_{per} = M_{act}/M </math>
 
with <math> M_{act}</math> being the number of activated bonds when the first cluster ''percolates'', and <math> M </math> is the number
of possible bonds.
 
The value of <math> p_{per} </math> (in one realisation, or the averaged value over the simulation, See the references for the
practical application)
can be related with the critical coupling constant, <math> k_c </math> as:
 
: <math> p_{per} \approx  1 - \exp \left[ - 2 k_c \right]  </math>


== Probability-Changing Cluster Algorithm ==
== Probability-Changing Cluster Algorithm ==
This method was proposed by Tomita and Okabe
<ref>[http://dx.doi.org/10.1103/PhysRevLett.86.572 Yusuke Tomita and Yutaka Okabe,  "Probability-Changing Cluster Algorithm for Potts Models", Physical Review Letters '''86''' pp. 572-575 (2001)]</ref>. This procedure is orientated towards computing [[critical points]].
It applies when the symmetry of the interactions imply that the critical
temperature is that in which the clusters, built using a Swendsen-Wang type algorithm, reach
the percolation threshold.
The simulation proceeds by a fine tuning of the temperature (or the coupling constant)
Given a configuration of the system and a current coupling constant <math> K_0 </math>:


#One builds  a bond realisation following the Swendsen-Wang strategy
This method was proposed by Tomita and Okabe (See Ref 4) and a few details will be given here soon ....
#One establishes whether at least one of the cluster percolates through the whole system
#If percolation occurs one decreases the coupling constant (increase the temperature) by a small amount <math> K^{new} = K_0 - \delta K </math>
#If no percolation appears, the new value of the coupling constant is taken to be <math> K^{new} = K_0 + \delta K </math>, with <math>\delta K > 0 </math>.  
 
For small values of <math> \delta K </math> the value of <math> K </math>
(after reaching the vicinity of the critical point) will show minor oscillations and the
results can be trusted to be those of an equilibrium simulation run. (note that [[Detailed balance |detailed balance]] is not
strictly fulfilled in this algorithm).


== Beyond the Ising and Potts models ==
== Beyond the Ising and Potts models ==


The methods described so far can be used, with minor changes, in the simulation of [[Potts model|Potts models]].
The methods described so far, can be used with minor changes in the simulation of [[Potts model|Potts models]].
In addition, extensions have been proposed in the literature  
In addition, extensions have been proposed in the literature (References will be added one of these days)
to build up very efficient cluster algorithms to simulate more complex lattice systems (for example the [[XY model]],  
to build up very efficient cluster algorithm to simulate more complex lattice systems ([[XY model]],  
[[Heisenberg model]], [[Lebwohl-Lasher model]]
[[Heisenberg model]], etc).
<ref>[http://dx.doi.org/10.1103/PhysRevE.63.062702 N. V. Priezjev and Robert A. Pelcovits "Cluster Monte Carlo simulations of the nematic-isotropic transition" Physical Review E '''63''' 062702 (2001)]</ref>, etc.)


== Application to continuous (atomistic) models ==
== Application to continuous (atomistic) models ==
It is sometimes possible (and very convenient) to include cluster algorithms in the  simulation of
It is sometimes possible (and very convenient) to include cluster algorithms in the  simulation of
models with continuous translational degrees of freedom. In most cases the cluster algorithm has
models with continuous trasnlational degrees of freedom. In most cases the cluster algorithm has
to be complemented with other sampling moves to ensure [[Ergodic hypothesis |ergodicity]]. Examples:
to be complemented with other sampling moves to ensure ''ergodicity''. Examples:
* Spin fluids
 
* Binary [[mixtures]] having interaction symmetry
* Spin fluids (more details soon)
* Continuous versions of the [[XY model]], [[Heisenberg model]], [[Lebwohl-Lasher model]], etc.
* Binary mixtures (with symmetry in the interactions) (examples soon)
* Continuous version of XY, Heisenberg, and similar models
(Some references will be included soon)
 
In these cases, the usual approach is to combine one-particle moves (e.g. particle translations),  
In these cases, the usual approach is to combine one-particle moves (e.g. particle translations),  
with cluster procedures. In the cluster steps, multiparticle modification of -composition, orientations, etc.-
with cluster procedures. In the cluster steps, multiparticle modification of -composition, orientations, etc.-
is carried out.
is carried out.


== Geometric cluster algorithms ==
== Other (not so smart) application of cluster algorithms ==
Geometric methods have been proposed for the efficient simulation of continuum fluids <ref>[http://dx.doi.org/10.1103/PhysRevLett.92.035504 Jiwen Liu and Erik Luijten, "Rejection-Free Geometric Cluster Algorithm for Complex Fluids", Physical Review Letters '''92''' 035504 (2004)]</ref> <ref> [http://dx.doi.org/10.1103/PhysRevE.71.066701 Jiwen Liu and Erik Luijten, "Generalized geometric cluster algorithm for fluid simulation",  Physical Review  E '''71''' 066701 (2005)]</ref>,
and have also been applied to simulations of [[mixtures]], <ref> [http://dx.doi.org/10.1063/1.1831274  Arnaud Buhot, "Cluster algorithm for nonadditive hard-core mixtures", Journal of Chemical Physics '''122''' 024105 (2005)] </ref>
such as [[colloids]] <ref>[http://dx.doi.org/10.1063/1.3495996 Douglas J. Ashton, Jiwen Liu, Erik Luijten, and Nigel B. Wilding "Monte Carlo cluster algorithm for fluid phase transitions in highly size-asymmetrical binary mixtures", Journal of Chemical Physics '''133''' 194102 (2010)]</ref>.
 
== Other applications of cluster algorithms ==
The cluster algorithms described so far are rejection-free methods, which means that every
new configuration generated throughout the sampling is accepted.
However, when the complexity of models increases, it becomes difficult to develop efficient
rejection-free algorithms. Nevertheless, in some cases it is still sometimes possible to build up quite efficient cluster algorithms.
 
Examples:
 
*Collective translations in the simulation of [[Micelles|micelles]]  <ref>[http://dx.doi.org/10.1021/j100189a030 David Wu, David Chandler and  Berend Smit, "Electrostatic analogy for surfactant assemblies", Journal of Physical Chemistry '''96'''  pp. 4077-4083 (1992)]</ref>
 
*Collective (cluster) translation/rotations in the simulation of the [[restricted primitive model|primitive model]] of electrolytes.<ref>
[http://dx.doi.org/10.1063/1.467770 Gerassimos Orkoulas and Athanassios Z. Panagiotopoulos, "Free energy and phase equilibria for the restricted primitive model of ionic fluids from Monte Carlo simulations", Journal of Chemical Physics '''101''' pp. 1452- (1994)]</ref>


*[[Monte Carlo|Monte Carlo]] simulation of atomistic systems with multiparticle moves.<ref>[http://dx.doi.org/10.1063/1.2759924  N. G. Almarza and E. Lomba "Cluster algorithm to perform parallel Monte Carlo simulation of atomistic systems", Journal of Chemical Physics '''127''' 084116 (2007)]</ref>.
* Monte Carlo simulation of atomistic systems with multiparticle moves:


*[[Monte Carlo|Monte Carlo]] simulation of [[Idealised models#'Hard' models | hard core models]] in the [[isothermal-isobaric ensemble|isothermal isobaric ensemble]].<ref>[http://dx.doi.org/10.1063/1.3133328 N. G. Almarza, "A cluster algorithm for Monte Carlo simulation at constant pressure", Journal of Chemical Physics '''130''', 184106 (2009) ]</ref>
[http://dx.doi.org/10.1063/1.2759924  N. G. Almarza and E. Lomba, ''Cluster algorithm to perform parallel Monte Carlo simulation of atomistic systems'', J, Chem. Phys (to appear) 2007 ]


== References ==
== References ==
<references/>
#[http://dx.doi.org/10.1103/PhysRevLett.58.86  Robert H. Swendsen and Jian-Sheng Wang, "Nonuniversal critical dynamics in Monte Carlo simulations", Physical Review Letters '''58''' pp. 86 - 88 (1987) ]
[[category: computer simulation techniques]]
#[http://dx.doi.org/10.1103/PhysRevLett.62.361 Ulli Wolff, "Collective Monte Carlo Updating for Spin Systems" , Physical Review Letters '''62''' pp. 361 - 364 (1989) ]
[[category: Monte Carlo]]
#[http://dx.doi.org/10.1103/PhysRevLett.75.2792    J. Machta, Y. S. Choi, A. Lucke,  T. Schweizer, and L. V. Chayes, "Invaded Cluster Algorithm for Equilibrium Critical Points" , Physical Review Letters '''75''' pp. 2792 - 2795 (1995)]
#[http://dx.doi.org/10.1103/PhysRevLett.86.572      Yusuke Tomita and Yutaka Okabe,  "Probability-Changing Cluster Algorithm for Potts Models", Physical Review Letters '''86''' pp. 572 - 575 (2001)]
Please note that all contributions to SklogWiki are considered to be released under the Creative Commons Attribution Non-Commercial Share Alike (see SklogWiki:Copyrights for details). If you do not want your writing to be edited mercilessly and redistributed at will, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource. Do not submit copyrighted work without permission!

To edit this page, please answer the question that appears below (more info):

Cancel Editing help (opens in new window)
Retrieved from "http://www.sklogwiki.org/SklogWiki/index.php/Cluster_algorithms"