Efficient implementation of the pivot algorithm for self-avoiding walks

Abstract

The pivot algorithm for self-avoiding walks has been implemented in a manner which is dramatically faster than previous implementations, enabling extremely long walks to be efficiently simulated. We explicitly describe the data structures and algorithms used, and provide a heuristic argument that the mean time per attempted pivot for $N$-step self-avoiding walks is $O(1)$ for the square and simple cubic lattices. Numerical experiments conducted for self-avoiding walks with up to 268 million steps are consistent with $o(\log N)$ behavior for the square lattice and $O(\log N)$ behavior for the simple cubic lattice. Our method can be adapted to other models of polymers with short-range interactions, on the lattice or in the continuum, and hence promises to be widely useful.

35 pages, 24 figures, 4 tables. Accepted for publication in the Journal of Statistical Physics.

References in corpus (1)

• Accurate estimate of the critical exponent $\nu$ for self-avoiding walks via a fast implementation of the pivot algorithm

Cited by in corpus (35)

• High-precision estimate of the hydrodynamic radius for self-avoiding walks
• Calculation of the connective constant for self-avoiding walks via the pivot algorithm
• Scale-free Monte Carlo method for calculating the critical exponent $\gamma$ of self-avoiding walks
• Geometrical Properties of Two-Dimensional Interacting Self-Avoiding Walks at the Theta-Point
• Low-Autocorrelation Binary Sequences: On Improved Merit Factors and Runtime Predictions to Achieve Them
• Fast, hierarchical, and adaptive algorithm for Metropolis Monte Carlo simulations of long-range interacting systems
• Polymers as compressible soft spheres
• Large Deviations of Convex Hulls of Self-Avoiding Random Walks
• The self-avoiding walk in a strip
• Three-dimensional terminally attached self-avoiding walks and bridges
• Coarse-graining polymer solutions: a critical appraisal of single- and multi-site models
• Polymer simulation by means of tree data-structures and a parsimonious Metropolis algorithm
• Scaling Analysis of Random Walks with Persistence Lengths: Application to Self-Avoiding Walks
• Logarithmic finite-size scaling of the self-avoiding walk at four dimensions
• Monte Carlo study of four-dimensional self-avoiding walks of up to one billion steps
• Self-avoiding walks and polygons -- an overview
• Theta-point polymers in the plane and Schramm-Loewner evolution
• Endless self-avoiding walks
• Consistent coarse-graining strategy for polymer solutions in the thermal crossover from Good to Theta solvent
• Simulating self-avoiding walks in bounded domains
• High resolution Monte Carlo study of the Domb-Joyce model
• Conformal invariance of the 3D self-avoiding walk
• Long Polymers Near Wedges and Cones
• Monte Carlo Simulation of Long Hard-Sphere Polymer Chains in Two to Five Dimensions
• Transforming fixed-length self-avoiding walks into radial SLE_8/3
• Polymer models with optimal good-solvent behavior
• A series test of the scaling limit of self-avoiding walks
• Off-lattice and parallel implementations of the pivot algorithm
• On Self-Avoiding Walks across n-Dimensional Dice and Combinatorial Optimization: An Introduction
• Topological comparison of flexible and semiflexible chains in polymer melts with $\theta$-chains
• Random knotting in very long off-lattice self-avoiding polygons
• Self-avoiding walks in a rectangle
• Winding angles of long lattice walks
• Scaling properties of diblock copolymers: dynamic simulations study
• The fixed irreducible bridge ensemble for self-avoiding walks