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:1703.03136 · Physical review. E

Geometric allocation approach to accelerating directed worm algorithm

Hidemaro Suwa

Published Jan 13, 2021• 4 citations
arXivHTMLPDF

Abstract

The worm algorithm is a versatile technique in the Markov chain Monte Carlo method for both classical and quantum systems. The algorithm substantially alleviates critical slowing down and reduces the dynamic critical exponents of various classical systems. It is crucial to improve the algorithm and push the boundary of the Monte Carlo method for physical systems. We here propose a directed worm algorithm that significantly improves computational efficiency. We use the geometric allocation approach to optimize the worm scattering process: worm backscattering is averted, and forward scattering is favored. Our approach successfully enhances the diffusivity of the worm head (kink), which is evident in the probability distribution of the relative position of the two kinks. Performance improvement is demonstrated for the Ising model at the critical temperature by measurement of exponential autocorrelation times and asymptotic variances. The present worm update is approximately 25 times as efficient as the conventional worm update for the simple cubic lattice model. Surprisingly, our algorithm is even more efficient than the Wolff cluster algorithm, which is one of the best update algorithms. We estimate the dynamic critical exponent of the simple cubic lattice Ising model to be z≈0.27 in the worm update. The worm and the Wolff algorithms produce different exponents of the integrated autocorrelation time of the magnetic susceptibility estimator but the same exponent of the asymptotic variance. We also discuss how to quantify the computational efficiency of the Markov chain Monte Carlo method. Our approach can be applied to a wide range of physical systems, such as the |ϕ|^{4} model, the Potts model, the O(n) loop model, and lattice QCD.

DOI
10.1103/physreve.103.013308

Related papers

Lifted directed-worm algorithm

Hidemaro Suwa

Nonreversible Markov chains can outperform reversible chains in the Markov chain Monte Carlo method. Lifting is a versatile approach to introducing net stochastic flow in state space and constructing a nonreversible Markov chain. We present here an application of the lifting technique to the directed-worm algorithm. The transition probability of the worm update is optimized using the geometric allocation approach; the worm backscattering probability is minimized, and the stochastic flow breaking the detailed balance is maximized. We demonstrate the performance improvement over the previous worm and cluster algorithms for the four-dimensional hypercubic lattice Ising model. The sampling efficiency of the present algorithm is approximately 80, 5, and 1.7 times as high as those of the standard worm algorithm, the Wolff cluster algorithm, and the previous lifted worm algorithm, respectively. We estimate the dynamic critical exponent of the hypercubic lattice Ising model to be z≈0 in the worm and the Wolff cluster updates. The lifted version of the directed-worm algorithm can be applied to a variety of quantum systems as well as classical systems.

arXiv:2206.13881•Physical review. E•Nov 9, 2022•2 citations

Measuring the efficiency of the Worm algorithm and the Metropolis algorithm in producing statistically independent observations

Lauri A. Lehtimäki

In lattice field theories the partition function is often a very high dimensional integral which can’t be written in a closed form. In order to study the behaviour of the system one needs an efficient algorithm to approximate the high dimensional integral. In this thesis two Markov chain Monte Carlo algorithms the Metropolis algorithm and the Worm algorithm are used to simulate the three dimensional xy-model near its critical point. As the critical point is approached from below in terms of the inverse coupling the correlation length of the system diverges which may lead to the critical slowing down. An efficient algorithm is such that it suffers from the critical slowing down as little as possible which corresponds to a small dynamical critical exponent value. The efficiency of the algorithms is compared by measuring the integrated autocorrelation time of energy for different lattice sizes. The dynamical critical exponent, which controls the computational cost of the simulation, is calculated as a linear least squares fit to the integrated autocorrelation time data. From the simulated data the measured value of the dynamical critical exponent for the Metropolis algorithm is 1.85 and for the Worm algorithm the value is 0.37.

Työväentutkimus Vuosikirja•Jan 1, 2018•0 citations

Worm Algorithms for Classical Statistical Models

Nikolay V. Prokof'ev, Boris V. Svistunov

We show that high-temperature expansions provide a basis for the novel approach to efficient Monte Carlo simulations. "Worm" algorithms utilize the idea of updating closed-path configurations (produced by high-temperature expansions) through the motion of end points of a disconnected path. An amazing result is that local, Metropolis-type schemes using this approach appear to have dynamical critical exponents close to zero (i.e., their efficiency is comparable to the best cluster methods) as proved by finite-size scaling of the autocorrelation time for various universality classes.

arXiv:cond-mat/0103146•Physical Review Letters•Sep 27, 2001•359 citations

Directed geometrical worm algorithm applied to the quantum rotor model

Fabien Alet, Erik Schwartz Sørensen

We discuss the implementation of a directed geometrical worm algorithm for the study of quantum link-current models. In this algorithm the Monte Carlo updates are made through the biased reptation of a worm through the lattice. A directed algorithm is an algorithm where, during the construction of the worm, the probability for erasing the immediately preceding part of the worm, when adding a new part, is minimal. We introduce a simple numerical procedure for minimizing this probability. The procedure only depends on appropriately defined local probabilities and should be generally applicable. Furthermore, we show how correlation functions C(r,tau) can be straightforwardly obtained from the probability of a worm to reach a site (r,tau) away from its starting point independent of whether or not a directed version of the algorithm is used. Detailed analytical proofs of the validity of the Monte Carlo algorithms are presented for both the directed and undirected geometrical worm algorithms. Results for autocorrelation times and Green's functions are presented for the quantum rotor model.

arXiv:cond-mat/0303080•Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics•Aug 12, 2003•42 citations

Single-cluster-update Monte Carlo method for the random anisotropy model

U. Rößler

A Wolff-type cluster Monte Carlo algorithm for random magnetic models is presented. The algorithm is demonstrated to reduce significantly the critical slowing down for planar random anisotropy models with weak anisotropy strength. Dynamic exponents $z\ensuremath{\lesssim}1.0$ of best cluster algorithms are estimated for models with ratio of anisotropy to exchange constant $D/J=1.0$ on cubic lattices in three dimensions. For these models, critical exponents are derived from a finite-size scaling analysis.

Physical review. B, Condensed matter•Jun 1, 1999•9 citations

Dual geometric worm algorithm for two-dimensional discrete classical lattice models

Peter B. Hitchcock, Erik Schwartz Sørensen, Fabien Alet

We present a dual geometrical worm algorithm for two-dimensional Ising models. The existence of such dual algorithms was first pointed out by Prokof'ev and Svistunov [Phys. Rev. Lett. 87, 160601 (2001)]]. The algorithm is defined on the dual lattice and is formulated in terms of bond variables and can therefore be generalized to other two-dimensional models that can be formulated in terms of bond variables. We also discuss two related algorithms formulated on the direct lattice, applicable in any dimension. These latter algorithms turn out to be less efficient but of considerable intrinsic interest. We show how such algorithms quite generally can be "directed" by minimizing the probability for the worms to erase themselves. Explicit proofs of detailed balance are given for all the algorithms. In terms of computational efficiency the dual geometrical worm algorithm is comparable to well known cluster algorithms such as the Swendsen-Wang and Wolff algorithms, however, it is quite different in structure and allows for a very simple and efficient implementation. The dual algorithm also allows for a very elegant way of calculating the domain wall free energy.

arXiv:cond-mat/0311011•Physical Review E•Jul 2, 2004•10 citations
The worm algorithm is a versatile technique in the Markov chain Monte Carlo method for both classical and quantum systems. The algorithm substantially alleviates critical slowing down and reduces the dynamic critical exponents of various classical systems. It is crucial to improve the algorithm and push the boundary of the Monte Carlo method for physical systems. We here propose a directed worm algorithm that significantly improves computational efficiency. We use the geometric allocation approach to optimize the worm scattering process: worm backscattering is averted, and forward scattering is favored. Our approach successfully enhances the diffusivity of the worm head (kink), which is evident in the probability distribution of the relative position of the two kinks. Performance improvement is demonstrated for the Ising model at the critical temperature by measurement of exponential autocorrelation times and asymptotic variances. The present worm update is approximately 25 times as efficient as the conventional worm update for the simple cubic lattice model. Surprisingly, our algorithm is even more efficient than the Wolff cluster algorithm, which is one of the best update algorithms. We estimate the dynamic critical exponent of the simple cubic lattice Ising model to be z≈0.27 in the worm update. The worm and the Wolff algorithms produce different exponents of the integrated autocorrelation time of the magnetic susceptibility estimator but the same exponent of the asymptotic variance. We also discuss how to quantify the computational efficiency of the Markov chain Monte Carlo method. Our approach can be applied to a wide range of physical systems, such as the |ϕ|^{4} model, the Potts model, the O(n) loop model, and lattice QCD.
Nonreversible Markov chains can outperform reversible chains in the Markov chain Monte Carlo method. Lifting is a versatile approach to introducing net stochastic flow in state space and constructing a nonreversible Markov chain. We present here an application of the lifting technique to the directed-worm algorithm. The transition probability of the worm update is optimized using the geometric allocation approach; the worm backscattering probability is minimized, and the stochastic flow breaking the detailed balance is maximized. We demonstrate the performance improvement over the previous worm and cluster algorithms for the four-dimensional hypercubic lattice Ising model. The sampling efficiency of the present algorithm is approximately 80, 5, and 1.7 times as high as those of the standard worm algorithm, the Wolff cluster algorithm, and the previous lifted worm algorithm, respectively. We estimate the dynamic critical exponent of the hypercubic lattice Ising model to be z≈0 in the worm and the Wolff cluster updates. The lifted version of the directed-worm algorithm can be applied to a variety of quantum systems as well as classical systems.
In lattice field theories the partition function is often a very high dimensional integral which can’t be written in a closed form. In order to study the behaviour of the system one needs an efficient algorithm to approximate the high dimensional integral. In this thesis two Markov chain Monte Carlo algorithms the Metropolis algorithm and the Worm algorithm are used to simulate the three dimensional xy-model near its critical point. As the critical point is approached from below in terms of the inverse coupling the correlation length of the system diverges which may lead to the critical slowing down. An efficient algorithm is such that it suffers from the critical slowing down as little as possible which corresponds to a small dynamical critical exponent value. The efficiency of the algorithms is compared by measuring the integrated autocorrelation time of energy for different lattice sizes. The dynamical critical exponent, which controls the computational cost of the simulation, is calculated as a linear least squares fit to the integrated autocorrelation time data. From the simulated data the measured value of the dynamical critical exponent for the Metropolis algorithm is 1.85 and for the Worm algorithm the value is 0.37.
We show that high-temperature expansions provide a basis for the novel approach to efficient Monte Carlo simulations. "Worm" algorithms utilize the idea of updating closed-path configurations (produced by high-temperature expansions) through the motion of end points of a disconnected path. An amazing result is that local, Metropolis-type schemes using this approach appear to have dynamical critical exponents close to zero (i.e., their efficiency is comparable to the best cluster methods) as proved by finite-size scaling of the autocorrelation time for various universality classes.
We discuss the implementation of a directed geometrical worm algorithm for the study of quantum link-current models. In this algorithm the Monte Carlo updates are made through the biased reptation of a worm through the lattice. A directed algorithm is an algorithm where, during the construction of the worm, the probability for erasing the immediately preceding part of the worm, when adding a new part, is minimal. We introduce a simple numerical procedure for minimizing this probability. The procedure only depends on appropriately defined local probabilities and should be generally applicable. Furthermore, we show how correlation functions C(r,tau) can be straightforwardly obtained from the probability of a worm to reach a site (r,tau) away from its starting point independent of whether or not a directed version of the algorithm is used. Detailed analytical proofs of the validity of the Monte Carlo algorithms are presented for both the directed and undirected geometrical worm algorithms. Results for autocorrelation times and Green's functions are presented for the quantum rotor model.
A Wolff-type cluster Monte Carlo algorithm for random magnetic models is presented. The algorithm is demonstrated to reduce significantly the critical slowing down for planar random anisotropy models with weak anisotropy strength. Dynamic exponents $z\ensuremath{\lesssim}1.0$ of best cluster algorithms are estimated for models with ratio of anisotropy to exchange constant D/J=1.0D/J=1.0D/J=1.0 on cubic lattices in three dimensions. For these models, critical exponents are derived from a finite-size scaling analysis.
We present a dual geometrical worm algorithm for two-dimensional Ising models. The existence of such dual algorithms was first pointed out by Prokof'ev and Svistunov [Phys. Rev. Lett. 87, 160601 (2001)]]. The algorithm is defined on the dual lattice and is formulated in terms of bond variables and can therefore be generalized to other two-dimensional models that can be formulated in terms of bond variables. We also discuss two related algorithms formulated on the direct lattice, applicable in any dimension. These latter algorithms turn out to be less efficient but of considerable intrinsic interest. We show how such algorithms quite generally can be "directed" by minimizing the probability for the worms to erase themselves. Explicit proofs of detailed balance are given for all the algorithms. In terms of computational efficiency the dual geometrical worm algorithm is comparable to well known cluster algorithms such as the Swendsen-Wang and Wolff algorithms, however, it is quite different in structure and allows for a very simple and efficient implementation. The dual algorithm also allows for a very elegant way of calculating the domain wall free energy.