Cluster algorithms: Difference between revisions

From SklogWiki
Jump to navigation Jump to search
mNo edit summary
Line 1: Line 1:
WORKING ON THIS PAGE ...
'''Cluster algorithms''' are mainly used in the simulation of [[Ising Models|Ising-like models]]. The essential feature is the use of collective motions
 
== Cluster algorithms in Monte Carlo Simulation.==
 
These 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.
of ''particles (spins)'' in a single Monte Carlo step.
An interesting property of some of these application is the fact that the [[percolation analysis]] of the clusters can
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 we shall discuss the Swendsen-Wang technique (Ref 1) in the simulation of [[Ising Models]].
As an introductory example we will discuss the Swendsen-Wang technique (Ref 1) in the simulation of [[Ising Models]].
 
=== Recipe ===  
=== Recipe ===  
In one Monte Carlo step of the algorithm the following recipe is used:
In one [[Monte Carlo]] step of the algorithm the following recipe is used:


* Consider every pair interacting sites (spins)
* Consider every pair interacting sites (spins)


In the current configuration the pair interaction can be either negative: <math> u_{ij}/k_B T= -K  </math> of positive <math> u_{ij}/k_B T = + K </math>,  
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 [[Ising Models]] for details on the notation)
depending on the product: <math> S_{i} S_{j} </math> (See [[Ising Models]] for details on the notation)


* For pairs of interacting sites (nearest neighbors) with <math> u_{ij}/k_B T < 0 </math> create a bond between the two spins with a given probability <math> p </math> (using [[random numbers]])
* 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>  
: <math> p </math> will be chosen to be a function of <math> K </math>  
Line 51: Line 44:
The bonded sites are included in the cluster
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
* 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.
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)
* At this point, the whole cluster is flipped (see above)
Line 59: Line 51:
(See Ref 3)
(See Ref 3)


The purpose of this algorithm is to locate critical points (critical temperature). So, in this case
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 probability of bonding neighboring sites with equal spins is not set ''a priori''.


to be continued...


== Probability-Changing Cluster Algorithm ==
== Probability-Changing Cluster Algorithm ==
Line 70: Line 61:
== Beyond the Ising and Potts models ==
== Beyond the Ising and Potts models ==


to be written
 


== Application to continuous (atomistic) models ==
== Application to continuous (atomistic) models ==


== 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'', Phys. Rev. Lett. 58, 86 - 88 (1987) ]
#[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'' , Phys. Rev. Lett. 62, 361 - 364 (1989) ]
#[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'' , Phys. Rev. Lett. 75, 2792 - 2795 (1995)]
#[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'', Phys. Rev. Lett. 86, 572 - 575 (2001)]
#[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)]

Revision as of 11:38, 7 August 2007

Cluster algorithms are mainly used in the simulation of 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 application is the fact that the percolation analysis of the clusters can be used to study phase transitions.

Swendsen-Wang algorithm

As an introductory example we shall discuss the Swendsen-Wang technique (Ref 1) in the simulation of Ising Models.

Recipe

In one Monte Carlo step of the algorithm the following recipe is used:

  • Consider every pair interacting sites (spins)

In the current configuration the pair interaction can be either negative: or positive , depending on the product: (See Ising Models for details on the notation)

  • For pairs of interacting sites (nearest neighbors) with create a bond between the two spins with a given probability (using random numbers)
will be chosen to be a function of
  • 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 or )

  • For each cluster, independently, choose at random with equal probabilities whether to flip (invert the value of ) or not to flip the whole set of spins belonging to the cluster.


The bonding probability is given by:

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 whole set of interacting pairs is not tested to generate (possible) bonds. In stead, a single cluster is built.

  • 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.
  • At this point, the whole cluster is flipped (see above)

Invaded Cluster Algorithm

(See Ref 3)

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.


Probability-Changing Cluster Algorithm

This method was proposed by Tomita and Okabe (See Ref 4)

Beyond the Ising and Potts models

Application to continuous (atomistic) models

References

  1. Robert H. Swendsen and Jian-Sheng Wang, Nonuniversal critical dynamics in Monte Carlo simulations, Physical Review Letters 58 pp. 86 - 88 (1987)
  2. Ulli Wolff, Collective Monte Carlo Updating for Spin Systems , Physical Review Letters 62 pp. 361 - 364 (1989)
  3. 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)
  4. Yusuke Tomita and Yutaka Okabe, Probability-Changing Cluster Algorithm for Potts Models, Physical Review Letters 86 pp. 572 - 575 (2001)