A faster implementation of the pivot algorithm for self-avoiding walks

Abstract

The pivot algorithm is a Markov Chain Monte Carlo algorithm for simulating the self-avoiding walk. At each iteration a pivot which produces a global change in the walk is proposed. If the resulting walk is self-avoiding, the new walk is accepted; otherwise, it is rejected. Past implementations of the algorithm required a time O(N) per accepted pivot, where N is the number of steps in the walk. We show how to implement the algorithm so that the time required per accepted pivot is O(N^q) with q<1. We estimate that q is less than 0.57 in two dimensions, and less than 0.85 in three dimensions. Corrections to the O(N^q) make an accurate estimate of q impossible. They also imply that the asymptotic behavior of O(N^q) cannot be seen for walk lengths which can be simulated. In simulations the effective q is around 0.7 in two dimensions and 0.9 in three dimensions. Comparisons with simulations that use the standard implementation of the pivot algorithm using a hash table indicate that our implementation is faster by as much as a factor of 80 in two dimensions and as much as a factor of 7 in three dimensions. Our method does not require the use of a hash table and should also be applicable to the pivot algorithm for off-lattice models.

24 pages, 7 figures

References in corpus (2)

• Critical Exponents, Hyperscaling and Universal Amplitude Ratios for Two- and Three-Dimensional Self-Avoiding Walks
• High-precision determination of the critical exponent gamma for self-avoiding walks

Cited by in corpus (13)

• Efficient implementation of the pivot algorithm for self-avoiding walks
• Conformal Invariance and Stochastic Loewner Evolution Predictions for the 2D Self-Avoiding Walk - Monte Carlo Tests
• Scale-free Monte Carlo method for calculating the critical exponent $\gamma$ of self-avoiding walks
• Computing the Loewner driving process of random curves in the half plane
• Three-dimensional terminally attached self-avoiding walks and bridges
• The Length of an SLE - Monte Carlo Studies
• Dynamic Critical Behavior of an Extended Reptation Dynamics for Self-Avoiding Walks
• Exact sampling of self-avoiding paths via discrete Schramm-Loewner evolution
• On the importance sampling of self-avoiding walks
• Weakly directed self-avoiding walks
• Endless self-avoiding walks
• Theta-point polymers in the plane and Schramm-Loewner evolution
• Efficiency of the Incomplete Enumeration algorithm for Monte-Carlo simulation of linear and branched polymers