Editing Cluster algorithms
Jump to navigation
Jump to search
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]] | '''Cluster algorithms''' are mainly used in the simulation of [[Ising Models|Ising-like models]]. The essential feature is the use of collective motions of particles (spins) in a single [[Monte Carlo]] step. | ||
An interesting property of some of these | 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]]. | 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 to the Swendsen-Wang algorithm we shall discuss the technique (Ref 1) in the simulation of the | ||
in the simulation of the | |||
[[Ising Models |Ising model]]. 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: | ||
Line 17: | Line 15: | ||
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. Instead, a single cluster | ||
is built. See | is built. See Ref 2 for details. | ||
for details. | |||
* The initial cluster contains one site, which is selected at random. | |||
* 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]] ( | The purpose of this algorithm is to locate [[critical points]] (critical temperature). So, in this case | ||
the probability of bonding neighbouring sites with equal spins is not set ''a priori'' (See | the probability of bonding neighbouring sites with equal spins is not set ''a priori''. (See Ref 3) | ||
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 on the system (pairs of nearest neighbours with favourable interaction) | |||
* Using [[random numbers]] one assigns a random order to these possible bonds | |||
* The possible bonds are being ''activated'' in the order fixed in the previous step (the cluster structure is watched during this process) | |||
* 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) | |||
* 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 | This method was proposed by Tomita and Okabe (See Ref 4). This procedure is orientated towards computing [[critical points]]. | ||
It applies when the symmetry of the interactions imply that the critical | 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 | temperature is that in which the clusters, built using a Swendsen-Wang type algorithm, reach | ||
Line 51: | Line 62: | ||
Given a configuration of the system and a current coupling constant <math> K_0 </math>: | 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 | |||
* 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: | |||
For small values of <math> \delta K </math> the value of <math> K </math> | : <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 | (after reaching the vicinity of the critical point) will show minor oscillations and the | ||
results can be trusted | results can be trusted as those of an equilibrium simulation run. ([[Detailed balance]] is not | ||
strictly fulfilled in this algorithm). | strictly fulfilled in this algorithm). | ||
Line 66: | Line 84: | ||
In addition, extensions have been proposed in the literature | In addition, extensions have been proposed in the literature | ||
to build up very efficient cluster algorithms to simulate more complex lattice systems (for example the [[XY model]], | to build up very efficient cluster algorithms to simulate more complex lattice systems (for example the [[XY model]], | ||
[[Heisenberg model]], | [[Heisenberg model]], 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 translational degrees of freedom. In most cases the cluster algorithm has | ||
to be complemented with other sampling moves to ensure [[ | to be complemented with other sampling moves to ensure [[ergodicity]]. Examples: | ||
* Spin fluids | * Spin fluids | ||
* | * [[Binary mixtures]] (with symmetry in the interactions) | ||
* Continuous | * Continuous version of [[XY model]], [[Heisenberg model]], etc. | ||
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. | ||
== | == Other (not so smart) applications of cluster algorithms == | ||
Monte Carlo simulation of atomistic systems with multiparticle moves, for example see: | |||
* | *[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)] | ||
== 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) ] | |||
[[ | #[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) ] | ||
[ | #[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)] |