Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1307.6647 · Physical Review E

Efficient simulation of the random-cluster model

Eren Metin Elçi, Martin Weigel

Published Sep 16, 2013• 18 citations
arXivHTMLPDF

Abstract

The simulation of spin models close to critical points of continuous phase transitions is heavily impeded by the occurrence of critical slowing down. A number of cluster algorithms, usually based on the Fortuin-Kasteleyn representation of the Potts model, and suitable generalizations for continuous-spin models have been used to increase simulation efficiency. The first algorithm making use of this representation, suggested by Sweeny in 1983, has not found widespread adoption due to problems in its implementation. However, it has been recently shown that it is indeed more efficient in reducing critical slowing down than the more well-known algorithm due to Swendsen and Wang. Here, we present an efficient implementation of Sweeny's approach for the random-cluster model using recent algorithmic advances in dynamic connectivity algorithms.

DOI
10.1103/physreve.88.033303

Related papers

Cluster algorithm for Potts models with fixed spin densities

R. P. Bikker, G. T. Barkema

A cluster algorithm is presented for the simulation of the q-state Potts models in which the number of spins is conserved in each state. The algorithm constructs Fortuin-Kasteleyn cluster configurations from spin configurations, in a way identical to the Swendsen-Wang algorithm; the spin assignment to these clusters is, however, different, and conserves the number of spins for each state. Compared to traditional nonlocal spin-exchange algorithms, the cluster algorithm presented here suffers less from critical slowing down, and consequently is more efficient near the critical temperature.

arXiv:cond-mat/0005076•Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics•Oct 1, 2000•3 citations

Single-cluster dynamics for the random-cluster model

Youjin Deng, Xiaofeng Qian, Henk W. J. Blöte

We formulate a single-cluster Monte Carlo algorithm for the simulation of the random-cluster model. This algorithm is a generalization of the Wolff single-cluster method for the q-state Potts model to noninteger values q>1. Its results for static quantities are in a satisfactory agreement with those of the existing Swendsen-Wang-Chayes-Machta (SWCM) algorithm, which involves a full-cluster decomposition of random-cluster configurations. We explore the critical dynamics of this algorithm for several two-dimensional Potts and random-cluster models. For integer q, the single-cluster algorithm can be reduced to the Wolff algorithm, for which case we find that the autocorrelation functions decay almost purely exponentially, with dynamic exponents z(exp)=0.07 (1), 0.521 (7), and 1.007 (9) for q=2, 3, and 4, respectively. For noninteger q, the dynamical behavior of the single-cluster algorithm appears to be very dissimilar to that of the SWCM algorithm. For large critical systems, the autocorrelation function displays a range of power-law behavior as a function of time. The dynamic exponents are relatively large. We provide an explanation for this peculiar dynamic behavior.

arXiv:0907.1711•Physical Review E•Sep 30, 2009•4 citations

Fixed-cluster acceleration algorithm for spin systems

Tanniemola B. Liverpool, Sharon C. Glotzer

A recently introduced cluster acceleration algorithm for spin models [J. Machta et al., Phys. Rev. Lett. 75, 2792 (1995)] based on invasion percolation is generalized to temperatures away from the critical point using concepts of random bond percolation. The generalized algorithm is equivalent to an "optimized" version of the Swendsen-Wang cluster algorithm [R. H. Swendsen and J. S. Wang, Phys. Rev. Lett. 58, 86 (1987)], and we demonstrate its success and speed at all temperatures for the $d=2$ Ising model. We argue that the previously discussed connection to self-organized criticality may be viewed as one limit of the fixed-cluster algorithm.

Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics•May 1, 1996•14 citations

Acceleration Algorithms in Monte Carlo Simulations in Statistical Physics

Robert H. Swendsen

Monte Carlo simulations of thermodynamic phase transitions are usually hampered by long relaxation times due to the phenomenon of “critical slowing down.” Using a mapping due to Fortuin and Kasteleyn, a cluster approach to Monte Carlo simulations has been developed, which greatly reduces relaxation times, improving efficiency by up to two or three orders of magnitude. New developments and extensions of this approach are also discussed.

International Journal of Modern Physics C•Mar 1, 1991•1 citation

Sweeny and Gliozzi dynamics for simulations of Potts models in the Fortuin-Kasteleyn representation

Jian‐Sheng Wang, Oner Kozan, Robert H. Swendsen

We compare the correlation times of the Sweeny and Gliozzi dynamics for two-dimensional Ising and three-state Potts models, and the three-dimensional Ising model for the simulations in the percolation representation. The results are also compared with Swendsen-Wang and Wolff cluster dynamics. It is found that Sweeny and Gliozzi dynamics have essentially the same dynamical critical behavior. Contrary to Gliozzi's claim [Phys. Rev. E 66, 016115 (2002)], the Gliozzi dynamics has critical slowing down comparable to that of other cluster methods. For the two-dimensional Ising model, both Sweeny and Gliozzi dynamics give good fits to logarithmic size dependences for the correlation times; for two-dimensional three-state Potts model, their dynamical critical exponent z is 0.49+/-0.01; the three-dimensional Ising model has z=0.37+/-0.02.

arXiv:cond-mat/0206437•Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics•Nov 6, 2002•15 citations

Critical Speeding-Up in the Local Dynamics of the Random-Cluster Model

Youjin Deng, Timothy M. Garoni, Alan D. Sokal

We study the dynamic critical behavior of the local bond-update (Sweeny) dynamics for the Fortuin-Kasteleyn random-cluster model in dimensions d=2, 3 by Monte Carlo simulation. We show that, for a suitable range of q values, the global observable S2 exhibits "critical speeding-up": it decorrelates well on time scales much less than one sweep. In some cases the dynamic critical exponent for the integrated autocorrelation time is negative. We also show that the dynamic critical exponent zexp is very close (possibly equal) to the rigorous lower bound alpha/nu and quite possibly smaller than the corresponding exponent for the Chayes-Machta-Swendsen-Wang cluster dynamics.

arXiv:cond-mat/0701113•Physical Review Letters•Jun 7, 2007•24 citations
The simulation of spin models close to critical points of continuous phase transitions is heavily impeded by the occurrence of critical slowing down. A number of cluster algorithms, usually based on the Fortuin-Kasteleyn representation of the Potts model, and suitable generalizations for continuous-spin models have been used to increase simulation efficiency. The first algorithm making use of this representation, suggested by Sweeny in 1983, has not found widespread adoption due to problems in its implementation. However, it has been recently shown that it is indeed more efficient in reducing critical slowing down than the more well-known algorithm due to Swendsen and Wang. Here, we present an efficient implementation of Sweeny's approach for the random-cluster model using recent algorithmic advances in dynamic connectivity algorithms.
A cluster algorithm is presented for the simulation of the q-state Potts models in which the number of spins is conserved in each state. The algorithm constructs Fortuin-Kasteleyn cluster configurations from spin configurations, in a way identical to the Swendsen-Wang algorithm; the spin assignment to these clusters is, however, different, and conserves the number of spins for each state. Compared to traditional nonlocal spin-exchange algorithms, the cluster algorithm presented here suffers less from critical slowing down, and consequently is more efficient near the critical temperature.
We formulate a single-cluster Monte Carlo algorithm for the simulation of the random-cluster model. This algorithm is a generalization of the Wolff single-cluster method for the q-state Potts model to noninteger values q>1. Its results for static quantities are in a satisfactory agreement with those of the existing Swendsen-Wang-Chayes-Machta (SWCM) algorithm, which involves a full-cluster decomposition of random-cluster configurations. We explore the critical dynamics of this algorithm for several two-dimensional Potts and random-cluster models. For integer q, the single-cluster algorithm can be reduced to the Wolff algorithm, for which case we find that the autocorrelation functions decay almost purely exponentially, with dynamic exponents z(exp)=0.07 (1), 0.521 (7), and 1.007 (9) for q=2, 3, and 4, respectively. For noninteger q, the dynamical behavior of the single-cluster algorithm appears to be very dissimilar to that of the SWCM algorithm. For large critical systems, the autocorrelation function displays a range of power-law behavior as a function of time. The dynamic exponents are relatively large. We provide an explanation for this peculiar dynamic behavior.
A recently introduced cluster acceleration algorithm for spin models [J. Machta et al., Phys. Rev. Lett. 75, 2792 (1995)] based on invasion percolation is generalized to temperatures away from the critical point using concepts of random bond percolation. The generalized algorithm is equivalent to an "optimized" version of the Swendsen-Wang cluster algorithm [R. H. Swendsen and J. S. Wang, Phys. Rev. Lett. 58, 86 (1987)], and we demonstrate its success and speed at all temperatures for the d=2d=2d=2 Ising model. We argue that the previously discussed connection to self-organized criticality may be viewed as one limit of the fixed-cluster algorithm.
We compare the correlation times of the Sweeny and Gliozzi dynamics for two-dimensional Ising and three-state Potts models, and the three-dimensional Ising model for the simulations in the percolation representation. The results are also compared with Swendsen-Wang and Wolff cluster dynamics. It is found that Sweeny and Gliozzi dynamics have essentially the same dynamical critical behavior. Contrary to Gliozzi's claim [Phys. Rev. E 66, 016115 (2002)], the Gliozzi dynamics has critical slowing down comparable to that of other cluster methods. For the two-dimensional Ising model, both Sweeny and Gliozzi dynamics give good fits to logarithmic size dependences for the correlation times; for two-dimensional three-state Potts model, their dynamical critical exponent z is 0.49+/-0.01; the three-dimensional Ising model has z=0.37+/-0.02.
We study the dynamic critical behavior of the local bond-update (Sweeny) dynamics for the Fortuin-Kasteleyn random-cluster model in dimensions d=2, 3 by Monte Carlo simulation. We show that, for a suitable range of q values, the global observable S2 exhibits "critical speeding-up": it decorrelates well on time scales much less than one sweep. In some cases the dynamic critical exponent for the integrated autocorrelation time is negative. We also show that the dynamic critical exponent zexp is very close (possibly equal) to the rigorous lower bound alpha/nu and quite possibly smaller than the corresponding exponent for the Chayes-Machta-Swendsen-Wang cluster dynamics.