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

Nuclear Physics B - Proceedings Supplements

Parallel cluster algorithms

Paul David Coddington, CLIVE F. BAILLIE

Published May 1, 1991• 4 citations
Publisher

Abstract

Cluster update algorithms dramatically reduce critical slowing down in spin models, but unlike the standard Metropolis algorithm, it is not obvious how to implement these algorithms efficiently on parallel or vector computers. Here we present two different parallel implementations of the Swendsen-Wang algorithm which give reasonable efficiencies on various MIMD parallel computers.

DOI
10.1016/0920-5632(91)90884-h

Related papers

Cluster Algorithms for Spin Models on MIMD Parallel Computers

Paul David Coddington, CLIVE F. BAILLIE

Parallel computers are ideally suited to the Monte Carlo simulation of spin models using the standard Metropolis algorithm, since it is regular and local. However local algorithms have the major drawback that near a phase transition the number of sweeps needed to generate a statistically independent configuration increases as the square of the lattice size. New algorithms have recently been developed which dramatically reduce this `critical slowing down' by updating clusters of spins at a time. The highly irregular and non-local nature of these algorithms means that they are much more difficult to parallelize efficiently. Here we introduce the new cluster algorithms, explain some sequential algorithms for identifying and labelling connected clusters of spins, and then outline some parallel algorithms which have been implemented on MIMD machines. 1. Introduction Computer simulations are extremely useful in the study of spin models in condensed matter physics. In these models the spins ...

Distributed Memory Computing Conference•Aug 24, 2005•7 citations

Efficient simulation of the random-cluster model

Eren Metin Elçi, Martin Weigel

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.

arXiv:1307.6647•Physical Review E•Sep 16, 2013•17 citations

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

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•15 citations

A new efficient cluster algorithm for the Ising model

Matthias Nyfeler, Michele Pepe A, U.‐J. Wiese

Using D-theory we construct a new efficient cluster algorithm for the Ising model.The construction is very different from the standard Swendsen-Wang algorithm and related to worm algorithms.With the new algorithm we have measured the correlation function with high precision over a surprisingly large number of orders of magnitude.

arXiv:hep-lat/0510040•Proceedings of XXIIIrd International Symposium on Lattice Field Theory — PoS(LAT2005)•Dec 14, 2005•0 citations

Comparison of cluster algorithms for two-dimensional Potts models

CLIVE F. BAILLIE, Paul David Coddington

We have measured the dynamical critical exponent z for the Swendsen-Wang and the Wolff cluster update algorithms, as well as a number of variants of these algorithms, for the q=2 and q=3 Potts models in two dimensions. We find that although the autocorrelation times differ considerably between algorithms, the critical exponents are the same. For q=2, we find that although the data are better fitted by a logarithmic increase in the autocorrelation time with lattice size, they are also consistent with a power law with exponent z\ensuremath{\approxeq}0.25, especially if there are non-negligible corrections to scaling.

Physical review. B, Condensed matter•May 1, 1991•74 citations
Cluster update algorithms dramatically reduce critical slowing down in spin models, but unlike the standard Metropolis algorithm, it is not obvious how to implement these algorithms efficiently on parallel or vector computers. Here we present two different parallel implementations of the Swendsen-Wang algorithm which give reasonable efficiencies on various MIMD parallel computers.
Parallel computers are ideally suited to the Monte Carlo simulation of spin models using the standard Metropolis algorithm, since it is regular and local. However local algorithms have the major drawback that near a phase transition the number of sweeps needed to generate a statistically independent configuration increases as the square of the lattice size. New algorithms have recently been developed which dramatically reduce this `critical slowing down' by updating clusters of spins at a time. The highly irregular and non-local nature of these algorithms means that they are much more difficult to parallelize efficiently. Here we introduce the new cluster algorithms, explain some sequential algorithms for identifying and labelling connected clusters of spins, and then outline some parallel algorithms which have been implemented on MIMD machines. 1. Introduction Computer simulations are extremely useful in the study of spin models in condensed matter physics. In these models the spins ...
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.
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 have measured the dynamical critical exponent z for the Swendsen-Wang and the Wolff cluster update algorithms, as well as a number of variants of these algorithms, for the q=2 and q=3 Potts models in two dimensions. We find that although the autocorrelation times differ considerably between algorithms, the critical exponents are the same. For q=2, we find that although the data are better fitted by a logarithmic increase in the autocorrelation time with lattice size, they are also consistent with a power law with exponent z\ensuremath{\approxeq}0.25, especially if there are non-negligible corrections to scaling.