arXiv:cond-mat/0103146 · Physical Review Letters

Worm Algorithms for Classical Statistical Models

Nikolay V. Prokof'ev, Boris V. Svistunov

Published Sep 27, 2001• 359 citations

Abstract

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.

DOI: 10.1103/physrevlett.87.160601

Related papers

Worm Algorithm for Problems of Quantum and Classical Statistics

Nikolay V. Prokof'ev

Theoretical studies often involve mappings of the original system onto an equivalent description in terms of abstract mathematical/graphical objects, where ‘equivalent’ means one obtains the same ﬁnal answer for some particular property. Path integrals, high-temperature expansions, and Feynman diagrams are the well-known examples considered in this chapter. Under such mappings, one has to deal with the inﬁnite-dimensional conﬁguration space having complex topology and non-local constraints which severely reduce efﬁciency of Monte Carlo simulations based on standard local updates. This sometimes leads to ergodicity problems in large systems when the entire conﬁguration space can not be sampled in a reasonable computation time. A somewhat related diﬃculty facing conventional Monte Carlo schemes is the computation of oﬀ-diagonal correlation functions since they have no direct relation to the conﬁguration space of the partition function. In what follows we consider path integrals for lattice and continuous systems, high-temperature expansions, and Feynman diagrams, explain the general idea of how Worm Algorithms (WAs) deal with the topological constraints by going to the enlarged conﬁguration space, and present illustrative results for several physics problems.

CRC Press eBooksNov 2, 20103 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 VuosikirjaJan 1, 20180 citations

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.03136Physical review. EJan 13, 20214 citations

Efficient and scalable path integral Monte Carlo simulations with worm-type updates for Bose-Hubbard and XXZ models

Nicolas Sadoune, Lode Pollet

We present a novel and open-source implementation of the worm algorithm, which is an algorithm to simulate Bose-Hubbard and sign-positive spin models using a path-integral representation of the partition function. The code can deal with arbitrary lattice structures and assumes spin-exchange terms, or bosonic hopping amplitudes, between nearest-neighbor sites, and local or nearest-neighbor interactions of the density-density type. We explicitly demonstrate the near-linear scaling of the algorithm with respect to the system volume and the inverse temperature and analyze the autocorrelation times in the vicinity of a U(1) U ( 1 ) second order phase transition. The code is written in such a way that extensions to other lattice models as well as closely-related sign-positive models can be done straightforwardly on top of the provided framework.

arXiv:2204.12262SciPost Physics CodebasesNov 29, 202218 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/0703787Physical Review LettersSep 10, 200742 citations

1 High precision single-cluster Monte Carlo measurement of the critical exponents of the classical 3D Heisenberg model ∗

Christian Holm, Wolfhard Janke E, Höchstleistungsrechenzentrum Forschungszentrum Jülich

Monte Carlo simulations near the phase transition. We compute high precision estimates of the critical coupling Kc, Binder’s parameter U ∗ , and the critical exponents ν, β/ν, η, and α/ν, using extensively histogram reweighting and optimization techniques that allow us to keep control over the statistical errors. Measurements of the autocorrelation time show the expected reduction of critical slowing down at the phase transition as compared to local update algorithms. This allows simulations on significantly larger lattices than in previous studies and consequently a better control over systematic errors in finite-size scaling analyses. 1.

Jan 1, 19925 citations