© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:cond-mat/0311011 · Physical Review E

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

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

Published Jul 2, 2004• 10 citations

Abstract

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.

DOI: 10.1103/physreve.70.016702

Related papers

Geometric allocation approach to accelerating directed worm algorithm

Hidemaro Suwa

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.

arXiv:1703.03136•Physical review. E•Jan 13, 2021•4 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

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

Dynamic Critical Behavior of the Worm Algorithm for the Ising Model

Youjin Deng, Timothy M. Garoni, Alan D. Sokal

We study the dynamic critical behavior of the worm algorithm for the two- and three-dimensional Ising models, by Monte Carlo simulation. The autocorrelation functions exhibit an unusual three-time-scale behavior. As a practical matter, the worm algorithm is slightly more efficient than the Swendsen-Wang algorithm for simulating the two-point function of the three-dimensional Ising model.

arXiv:cond-mat/0703787•Physical Review Letters•Sep 10, 2007•42 citations

Lifted worm algorithm for the Ising model

Eren Metin Elçi, Jens Grimm, Lijie Ding +3 more

We design an irreversible worm algorithm for the zero-field ferromagnetic Ising model by using the lifting technique. We study the dynamic critical behavior of an energylike observable on both the complete graph and toroidal grids, and compare our findings with reversible algorithms such as the Prokof'ev-Svistunov worm algorithm. Our results show that the lifted worm algorithm improves the dynamic exponent of the energylike observable on the complete graph and leads to a significant constant improvement on toroidal grids.

arXiv:1711.05346•Physical review. E•Apr 18, 2018•12 citations

Efficient algorithm for computing correlation functions of the two-dimensional random-bond Ising model

Xintian Wu, Juan Zhao

Extending the recent work of the bond-propagation algorithm [Y. L. Loh and E. W. Carlson, Phys. Rev. Lett. 97, 227205 (2006)], we present an efficient algorithm for calculating the correlation functions between any two (or more) spins of Ising models in two dimensions. With this algorithm, the spontaneous magnetization, correlation length, and susceptibility can be calculated. The results for the usual Ising model with different size lattices are compared with the exact results. We also present the correlation functions for the $\ifmmode\pm\else\textpm\fi{}J$ random-bond Ising model.

Physical Review B•Sep 3, 2009•6 citations

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.

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.

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.

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.

We design an irreversible worm algorithm for the zero-field ferromagnetic Ising model by using the lifting technique. We study the dynamic critical behavior of an energylike observable on both the complete graph and toroidal grids, and compare our findings with reversible algorithms such as the Prokof'ev-Svistunov worm algorithm. Our results show that the lifted worm algorithm improves the dynamic exponent of the energylike observable on the complete graph and leads to a significant constant improvement on toroidal grids.

Extending the recent work of the bond-propagation algorithm [Y. L. Loh and E. W. Carlson, Phys. Rev. Lett. 97, 227205 (2006)], we present an efficient algorithm for calculating the correlation functions between any two (or more) spins of Ising models in two dimensions. With this algorithm, the spontaneous magnetization, correlation length, and susceptibility can be calculated. The results for the usual Ising model with different size lattices are compared with the exact results. We also present the correlation functions for the $\ifmmode\pm\else\textpm\fi{}J$ random-bond Ising model.