© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

AIP conference proceedings

The Development of Cluster and Histogram Methods

Robert H. Swendsen

Published Jan 1, 2003• 0 citations

Abstract

This talk will review the history of both cluster and histogram methods for Monte Carlo simulations. Cluster methods are based on the famous exact mapping by Fortuin and Kasteleyn from general Potts models onto a percolation representation. I will discuss the Swendsen‐Wang algorithm, as well as its improvement and extension to more general spin models by Wolff. The Replica Monte Carlo method further extended cluster simulations to deal with frustrated systems. The history of histograms is quite extensive, and can only be summarized briefly in this talk. It goes back at least to work by Salsburg et al. in 1959. Since then, it has been forgotten and rediscovered several times. The modern use of the method has exploited its ability to efficiently determine the location and height of peaks in various quantities, which is of prime importance in the analysis of critical phenomena. The extensions of this approach to the multiple histogram method and multicanonical ensembles have allowed information to be obtained over a broad range of parameters. Histogram simulations and analyses have become standard techniques in Monte Carlo simulations.

DOI: 10.1063/1.1632116

Related papers

Monte Carlo study of weighted percolation clusters relevant to the Potts models

M. Sweeny

The two-dimensional Potts models were simulated with the use of a Monte Carlo method. This study is unique in that we simulated the weighted percolation clusters first described by Kasteleyn and Fortuin in 1969. We describe an auxiliary data structure which enables us to determine the connectedness of large clusters very efficiently. Our simulation of the percolation problem was found not to be affected by a critical slowing down. Critical exponents were found by studying the size and shape of large clusters. Our results agree with previous studies done on integer values of $q$, and with the conjecture of den Nijs.

Physical review. B, Condensed matter•Apr 1, 1983•128 citations

Monte Carlo studies of magnetic critical phenomena using histogram techniques (invited)

Alan M. Ferrenberg, D. P. Landau, Pawel Peczak

Recent developments in the use of histograms (measured discrete probability distributions) now make it possible to determine critical properties with high accuracy using Monte Carlo (MC) simulations combined with finite-size scaling analyses. The advantages and limitations of the use of histograms for extracting the maximum information from MC simulation data are described. Results from extensive MC studies of the critical properties of two important magnetic systems, the d=3 ferromagnetic Ising and Heisenberg models, are presented. It is shown that the careful use of histogram techniques can provide results comparable or superior to these obtained with other numerical methods while maintaining all the advantages of standard MC techniques.

Journal of Applied Physics•Apr 15, 1991•5 citations

Cluster algorithms with empahsis on quantum spin systems

James E. Gubernatis, Naoki Kawashima

The purpose of this lecture is to discuss in detail the generalized approach of Kawashima and Gubernatis for the construction of cluster algorithms. We first present a brief refresher on the Monte Carlo method, describe the Swendsen-Wang algorithm, show how this algorithm follows from the Fortuin-Kastelyn transformation, and re=interpret this transformation in a form which is the basis of the generalized approach. We then derive the essential equations of the generalized approach. This derivation is remarkably simple if done from the viewpoint of probability theory, and the essential assumptions will be clearly stated. These assumptions are implicit in all useful cluster algorithms of which we are aware. They lead to a quite different perspective on cluster algorithms than found in the seminal works and in Ising model applications. Next, we illustrate how the generalized approach leads to a cluster algorithm for world-line quantum Monte Carlo simulations of Heisenberg models with S = 1/2. More succinctly, we also discuss the generalization of the Fortuin- Kasetelyn transformation to higher spin models and illustrate the essential steps for a S = 1 Heisenberg model. Finally, we summarize how to go beyond S = 1 to a general spin, XYZ model.

•Oct 6, 1995•0 citations

Virtual bond percolation for Ising cluster dynamics

Richard C. Brower, Pablo Tamayo

The Fortuin-Kasteleyn mapping between the Ising model and the site-bond correlated percolation model is shown to be only one of an infinite class of exact mappings. These new cluster representations are a result of "renormalized" percolation rules correlated to entire blocks of spins. For example these rules allow for percolation on "virtual" bonds between spins not present in the underlying Hamiltonian. As a consequence we can define new random cluster theories each with its own Monte Carlo cluster dynamics that exactly reproduce the Ising model. By tuning parameters on the critical percolation surface, it is demonstrated numerically that cluster algorithms can be formulated for the 2-d and 3-d Ising model that have smaller autocorrelations than the original Swendsen-Wang algorithm.

arXiv:hep-lat/9206007•Physica A Statistical Mechanics and its Applications•Apr 1, 1993•9 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

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

This talk will review the history of both cluster and histogram methods for Monte Carlo simulations. Cluster methods are based on the famous exact mapping by Fortuin and Kasteleyn from general Potts models onto a percolation representation. I will discuss the Swendsen‐Wang algorithm, as well as its improvement and extension to more general spin models by Wolff. The Replica Monte Carlo method further extended cluster simulations to deal with frustrated systems. The history of histograms is quite extensive, and can only be summarized briefly in this talk. It goes back at least to work by Salsburg et al. in 1959. Since then, it has been forgotten and rediscovered several times. The modern use of the method has exploited its ability to efficiently determine the location and height of peaks in various quantities, which is of prime importance in the analysis of critical phenomena. The extensions of this approach to the multiple histogram method and multicanonical ensembles have allowed information to be obtained over a broad range of parameters. Histogram simulations and analyses have become standard techniques in Monte Carlo simulations.

The two-dimensional Potts models were simulated with the use of a Monte Carlo method. This study is unique in that we simulated the weighted percolation clusters first described by Kasteleyn and Fortuin in 1969. We describe an auxiliary data structure which enables us to determine the connectedness of large clusters very efficiently. Our simulation of the percolation problem was found not to be affected by a critical slowing down. Critical exponents were found by studying the size and shape of large clusters. Our results agree with previous studies done on integer values of

q

, and with the conjecture of den Nijs.

Recent developments in the use of histograms (measured discrete probability distributions) now make it possible to determine critical properties with high accuracy using Monte Carlo (MC) simulations combined with finite-size scaling analyses. The advantages and limitations of the use of histograms for extracting the maximum information from MC simulation data are described. Results from extensive MC studies of the critical properties of two important magnetic systems, the d=3 ferromagnetic Ising and Heisenberg models, are presented. It is shown that the careful use of histogram techniques can provide results comparable or superior to these obtained with other numerical methods while maintaining all the advantages of standard MC techniques.

The purpose of this lecture is to discuss in detail the generalized approach of Kawashima and Gubernatis for the construction of cluster algorithms. We first present a brief refresher on the Monte Carlo method, describe the Swendsen-Wang algorithm, show how this algorithm follows from the Fortuin-Kastelyn transformation, and re=interpret this transformation in a form which is the basis of the generalized approach. We then derive the essential equations of the generalized approach. This derivation is remarkably simple if done from the viewpoint of probability theory, and the essential assumptions will be clearly stated. These assumptions are implicit in all useful cluster algorithms of which we are aware. They lead to a quite different perspective on cluster algorithms than found in the seminal works and in Ising model applications. Next, we illustrate how the generalized approach leads to a cluster algorithm for world-line quantum Monte Carlo simulations of Heisenberg models with S = 1/2. More succinctly, we also discuss the generalization of the Fortuin- Kasetelyn transformation to higher spin models and illustrate the essential steps for a S = 1 Heisenberg model. Finally, we summarize how to go beyond S = 1 to a general spin, XYZ model.

The Fortuin-Kasteleyn mapping between the Ising model and the site-bond correlated percolation model is shown to be only one of an infinite class of exact mappings. These new cluster representations are a result of "renormalized" percolation rules correlated to entire blocks of spins. For example these rules allow for percolation on "virtual" bonds between spins not present in the underlying Hamiltonian. As a consequence we can define new random cluster theories each with its own Monte Carlo cluster dynamics that exactly reproduce the Ising model. By tuning parameters on the critical percolation surface, it is demonstrated numerically that cluster algorithms can be formulated for the 2-d and 3-d Ising model that have smaller autocorrelations than the original Swendsen-Wang algorithm.

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.