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

Physical Review Letters

Rigorous lower bound on the dynamic critical exponent of some multilevel Swendsen-Wang algorithms

Xiao-Jian Li, Alan D. Sokal

Published Sep 16, 1991• 15 citations
Publisher

Abstract

We prove the rigorous lower bound ${\mathit{z}}_{\mathrm{exp}}$\ensuremath{\ge}\ensuremath{\alpha}/\ensuremath{\nu} for the dynamic critical exponent of a broad class of multilevel (or ``multigrid'') variants of the Swendsen-Wang algorithm. This proves that such algorithms do suffer from critical slowing down. We conjecture that such algorithms in fact lie in the same dynamic universality class as the stanard Swendsen-Wang algorithm.

DOI
10.1103/physrevlett.67.1482

Related papers

Rigorous lower bound on the dynamic critical exponents of the Swendsen-Wang algorithm

Xiao-Jian Li, Alan D. Sokal

We prove the rigorous lower bound ${z}_{\mathrm{sw}\ensuremath{\ge}\mathrm{\ensuremath{\alpha}}/\ensuremath{\nu}}$ for the dynamic critical exponent of the Swendsen-Wang algorithm. For two-dimensional q-state Potts models with q=2,3,4, this implies ${z}_{\mathrm{sw}\ensuremath{\ge}0}$,(2/5,1. We present numerical data indicating that ${z}_{\mathrm{sw}=0.55\ifmmode\pm\else\textpm\fi{}0.03}$, 0.89\ifmmode\pm\else\textpm\fi{}0.05 for q=3,4 (95% confidence limits, statistical errors only). The discrepancy for q=4 appears to be caused by multiplicative logarithmic corrections.

Physical Review Letters•Aug 21, 1989•105 citations

Empirical relations between static and dynamic exponents for Ising model cluster algorithms

Paul Coddington, CLIVE F. BAILLIE

We have measured the autocorrelations for the Swendsen-Wang and the Wolff cluster update algorithms for the Ising model in two, three, and four dimensions. The data for the Wolff algorithm suggest that the autocorrelations are linearly related to the specific heat, in which case the dynamic critical exponent is ${\mathit{z}}_{\mathrm{i}\mathrm{n}\mathrm{t},}$${\mathit{E}}^{\mathrm{W}}$=\ensuremath{\alpha}/\ensuremath{\nu}. For the Swendsen-Wang algorithm, scaling the autocorrelations by the average maximum cluster size gives either a constant or a logarithm, which implies that ${\mathit{z}}_{\mathrm{i}\mathrm{n}\mathrm{t},}$${\mathit{E}}^{\mathrm{SW}}$=\ensuremath{\beta}/\ensuremath{\nu} for the Ising model.

Physical Review Letters•Feb 17, 1992•46 citations

Dynamic critical exponents for Swendsen–Wang and Wolff algorithms obtained by a nonequilibrium relaxation method

Jianqing Du, Bo Zheng, Jian‐Sheng Wang

Using a nonequilibrium relaxation method, we calculate the dynamic critical exponent z of the two-dimensional Ising model for the Swendsen–Wang and Wolff algorithms. We examine dynamic relaxation processes following a quench from a disordered or an ordered initial state to the critical temperature T c , and measure the exponential relaxation time of the system energy. For the Swendsen–Wang algorithm with an ordered or a disordered initial state, and for the Wolff algorithm with an ordered initial state, the exponential relaxation time fits well to a logarithmic size dependence up to a lattice size L = 8192. For the Wolff algorithm with a disordered initial state, we obtain an effective dynamic exponent z exp = 1.19(2) up to L = 2048. For comparison, we also compute the effective dynamic exponents through the integrated correlation times. In addition, an exact result of the Swendsen–Wang dynamic spectrum of a one-dimensional Ising chain is derived.

arXiv:cond-mat/0603038•Journal of Statistical Mechanics Theory and Experiment•May 11, 2006•14 citations

Comparison of cluster algorithms for two-dimensional Potts models

CLIVE F. BAILLIE, Paul 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

Dynamic exponents for potts model cluster algorithms

Paul Coddington, CLIVE F. BAILLIE

We have studied the Swendsen-Wang and Wolff cluster update algorithms for the Ising model in 2, 3 and 4 dimensions. The data indicate simple relations between the specific heat and the Wolff autocorrelations, and between the magnetization and the Swendsen-Wang autocorrelations. This implies that the dynamic critical exponents are related to the static exponents of the Ising model. We also investigate the possibility of similar relationships for the Q-state Potts model.

Nuclear Physics B - Proceedings Supplements•Jan 1, 1992•1 citation

Dynamic critical behavior of cluster algorithms for 2D Ashkin-Teller and Potts models

Jesús Salas

We study the dynamic critical behavior of two algorithms: the Swendsen-Wang algorithm for the two-dimensional Potts model with q=2,3,4 and a Swendsen-Wang-type algorithm for the two-dimensional symmetric Ashkin-Teller model on the self-dual curve. We find that the Li--Sokal bound on the autocorrelation time τ_{{\rm int},{\cal E}} \geq const \times C_H is almost, but not quite sharp. The ratio τ_{{\rm int},{\cal E}}/C_H appears to tend to infinity either as a logarithm or as a small power (0.05 \ltapprox p \ltapprox 0.12). We also show that the exponential autocorrelation time τ_{{\rm exp},{\cal E}} is proportional to the integrated autocorrelation time τ_{{\rm int},{\cal E}}.

arXiv:cond-mat/0004329•Apr 19, 2000•3 citations
We prove the rigorous lower bound zexp{\mathit{z}}_{\mathrm{exp}}zexp​\ensuremath{\ge}\ensuremath{\alpha}/\ensuremath{\nu} for the dynamic critical exponent of a broad class of multilevel (or ``multigrid'') variants of the Swendsen-Wang algorithm. This proves that such algorithms do suffer from critical slowing down. We conjecture that such algorithms in fact lie in the same dynamic universality class as the stanard Swendsen-Wang algorithm.
We prove the rigorous lower bound ${z}_{\mathrm{sw}\ensuremath{\ge}\mathrm{\ensuremath{\alpha}}/\ensuremath{\nu}}$ for the dynamic critical exponent of the Swendsen-Wang algorithm. For two-dimensional q-state Potts models with q=2,3,4, this implies ${z}_{\mathrm{sw}\ensuremath{\ge}0}$,(2/5,1. We present numerical data indicating that ${z}_{\mathrm{sw}=0.55\ifmmode\pm\else\textpm\fi{}0.03}$, 0.89\ifmmode\pm\else\textpm\fi{}0.05 for q=3,4 (95% confidence limits, statistical errors only). The discrepancy for q=4 appears to be caused by multiplicative logarithmic corrections.
We have measured the autocorrelations for the Swendsen-Wang and the Wolff cluster update algorithms for the Ising model in two, three, and four dimensions. The data for the Wolff algorithm suggest that the autocorrelations are linearly related to the specific heat, in which case the dynamic critical exponent is zint,{\mathit{z}}_{\mathrm{i}\mathrm{n}\mathrm{t},}zint,​EW{\mathit{E}}^{\mathrm{W}}EW=\ensuremath{\alpha}/\ensuremath{\nu}. For the Swendsen-Wang algorithm, scaling the autocorrelations by the average maximum cluster size gives either a constant or a logarithm, which implies that zint,{\mathit{z}}_{\mathrm{i}\mathrm{n}\mathrm{t},}zint,​ESW{\mathit{E}}^{\mathrm{SW}}ESW=\ensuremath{\beta}/\ensuremath{\nu} for the Ising model.
Using a nonequilibrium relaxation method, we calculate the dynamic critical exponent z of the two-dimensional Ising model for the Swendsen–Wang and Wolff algorithms. We examine dynamic relaxation processes following a quench from a disordered or an ordered initial state to the critical temperature T c , and measure the exponential relaxation time of the system energy. For the Swendsen–Wang algorithm with an ordered or a disordered initial state, and for the Wolff algorithm with an ordered initial state, the exponential relaxation time fits well to a logarithmic size dependence up to a lattice size L = 8192. For the Wolff algorithm with a disordered initial state, we obtain an effective dynamic exponent z exp = 1.19(2) up to L = 2048. For comparison, we also compute the effective dynamic exponents through the integrated correlation times. In addition, an exact result of the Swendsen–Wang dynamic spectrum of a one-dimensional Ising chain is derived.
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.
We study the dynamic critical behavior of two algorithms: the Swendsen-Wang algorithm for the two-dimensional Potts model with q=2,3,4 and a Swendsen-Wang-type algorithm for the two-dimensional symmetric Ashkin-Teller model on the self-dual curve. We find that the Li--Sokal bound on the autocorrelation time τ_{{\rm int},{\cal E}} \geq const \times C_H is almost, but not quite sharp. The ratio τ_{{\rm int},{\cal E}}/C_H appears to tend to infinity either as a logarithm or as a small power (0.05 \ltapprox p \ltapprox 0.12). We also show that the exponential autocorrelation time τ_{{\rm exp},{\cal E}} is proportional to the integrated autocorrelation time τ_{{\rm int},{\cal E}}.