© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

Distributed Memory Computing Conference

Cluster Algorithms for Spin Models on MIMD Parallel Computers

Paul David Coddington, CLIVE F. BAILLIE

Published Aug 24, 2005• 7 citations

Abstract

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 ...

DOI: 10.1109/dmcc.1990.555410

Related papers

Parallel cluster algorithms

Paul David Coddington, CLIVE F. BAILLIE

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.

Nuclear Physics B - Proceedings Supplements•May 1, 1991•4 citations

MONTE CARLO METHODS IN SEQUENTIAL AND PARALLEL COMPUTING OF 2D AND 3D ISING MODEL

M. Diaconu, R. Puscasu, Alexandru Stancu +1 more

Because of its complexity, the 3D Ising model has not been given an exact analytic solution so far, as well as the 2D Ising in non zero external field conditions. In real materials the phase transition creates a discontinuity. We analysed the Ising model that presents similar discontinuities. We use Monte Carlo methods with a single spin change or a spin cluster change to calculate macroscopic quantities, such as specific heat and magnetic susceptibility. We studied the differences between these methods. Local MC algorithms (such as Metropolis) perform poorly for large lattices because they update only one spin at a time, so it takes many iterations to get a statistically independent configuration. More recent spin cluster algorithms use clever ways of finding clusters of sites that can be updated at once. The single cluster method is probably the best sequential cluster algorithm. We also used the entropic sampling method to simulate the density of states. This method takes into account all possible configurations, not only the most probable. The entropic method also gives good results in the 3D case. We studied the usefulness of distributed computing for Ising model. We established a parallelization strategy to explore Metropolis Monte Carlo simulation and Swendsen-Wang Monte Carlo simulation of this spin model using the data parallel languages on different platform. After building a computer cluster we made a Monte Carlo estimation of 2D and 3D Ising thermodynamic properties and compare the results with the sequential computing. In the same time we made quantitative analysis such as speed up and efficiency for different sets of combined parameters (e.g. lattice size, parallel algorithms, chosen model).

•Jan 1, 2003•0 citations

LATTICE SPIN MODELS AND NEW ALGORITHMS — A REVIEW OF MONTE CARLO COMPUTER SIMULATIONS

CLIVE F. BAILLIE

We review Monte Carlo computer simulations of spin models — both discrete and continuous. We explain the phenomenon of critical slowing which seriously degrades the efficiency of standard local Monte Carlo algorithms such as the Metropolis algorithm near phase transitions. We then go onto describe in detail the new algorithms which ameliorate the problem of critical slowing down, and give their dynamical critical exponent values.

International Journal of Modern Physics C•Apr 1, 1990•27 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

PARALLEL ACCELERATION ALGORITHM FOR SPIN MODELS

Gyan V Bhanot, Stephen L. Adler

We describe and implement a multi-scale acceleration algorithm for spin models on a massively parallel supercomputer, the Connection Machine CM-200. Unlike usual cluster algorithms, our algorithm is completely parallelizable. The time to update all variables in a system of volume Ld scales as Ld log 2L. We prove this by computing the time for one lattice sweep for the 2-d XY model for our algorithm on lattices of size up to 2048×2048.

International Journal of Modern Physics C•Aug 1, 1992•5 citations

Parallel-tempering cluster algorithm for computer simulations of critical phenomena

Elmar Bittner, Wolfhard Janke E

In finite-size scaling analyses of Monte Carlo simulations of second-order phase transitions one often needs an extended temperature range around the critical point. By combining the parallel-tempering algorithm with cluster updates and an adaptive routine to find the temperature window of interest, we introduce a flexible and powerful method for systematic investigations of critical phenomena. As a result, we gain one to two orders of magnitude in the performance for two- and three-dimensional Ising models in comparison with the recently proposed Wang-Landau recursion for cluster algorithms based on the multibondic algorithm, which is already a great improvement over the standard multicanonical variant.

arXiv:1107.5640•Physical Review E•Sep 1, 2011•15 citations

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 ...

Because of its complexity, the 3D Ising model has not been given an exact analytic solution so far, as well as the 2D Ising in non zero external field conditions. In real materials the phase transition creates a discontinuity. We analysed the Ising model that presents similar discontinuities. We use Monte Carlo methods with a single spin change or a spin cluster change to calculate macroscopic quantities, such as specific heat and magnetic susceptibility. We studied the differences between these methods. Local MC algorithms (such as Metropolis) perform poorly for large lattices because they update only one spin at a time, so it takes many iterations to get a statistically independent configuration. More recent spin cluster algorithms use clever ways of finding clusters of sites that can be updated at once. The single cluster method is probably the best sequential cluster algorithm. We also used the entropic sampling method to simulate the density of states. This method takes into account all possible configurations, not only the most probable. The entropic method also gives good results in the 3D case. We studied the usefulness of distributed computing for Ising model. We established a parallelization strategy to explore Metropolis Monte Carlo simulation and Swendsen-Wang Monte Carlo simulation of this spin model using the data parallel languages on different platform. After building a computer cluster we made a Monte Carlo estimation of 2D and 3D Ising thermodynamic properties and compare the results with the sequential computing. In the same time we made quantitative analysis such as speed up and efficiency for different sets of combined parameters (e.g. lattice size, parallel algorithms, chosen model).

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.

In finite-size scaling analyses of Monte Carlo simulations of second-order phase transitions one often needs an extended temperature range around the critical point. By combining the parallel-tempering algorithm with cluster updates and an adaptive routine to find the temperature window of interest, we introduce a flexible and powerful method for systematic investigations of critical phenomena. As a result, we gain one to two orders of magnitude in the performance for two- and three-dimensional Ising models in comparison with the recently proposed Wang-Landau recursion for cluster algorithms based on the multibondic algorithm, which is already a great improvement over the standard multicanonical variant.