Efficient implementation of the Pivot algorithm for self-avoiding walks

DOI10.1007/S10955-010-9994-8zbMATH Open1197.82057OpenAlexW2144056067MaRDI QIDQ5961852FDOQ5961852

Authors Nathan Clisby

Publication date 16 September 2010

Published in Journal of Statistical Physics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1005.1444

zbMATH Keywords

Monte Carloself-avoiding walkpivot algorithmpolymer

Mathematics Subject Classification ID

Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics (82B41) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Statistical mechanics of polymers (82D60)

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(logN)$ behavior for the square lattice and $O(logN)$ 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.

Recommendations

• A faster implementation of the pivot algorithm for self-avoiding walks
• The pivot algorithm: a highly efficient Monte Carlo method for the self-avoiding walk.
• The pivot algorithm and polygons: results on the FCC lattice
• Calculation of the connective constant for self-avoiding walks via the pivot algorithm
• Monte Carlo methods for the self-avoiding walk

Cites work

• scientific article; zbMATH DE number 1033260 (Why is no real title available?)
• scientific article; zbMATH DE number 1984686 (Why is no real title available?)
• scientific article; zbMATH DE number 2154241 (Why is no real title available?)
• scientific article; zbMATH DE number 201032 (Why is no real title available?)
• A faster implementation of the pivot algorithm for self-avoiding walks
• Cache-oblivious algorithms
• Correction-to-scaling exponents for two-dimensional self-avoiding walks
• Critical exponents, hyperscaling, and universal amplitude ratios for two- and three-dimensional self-avoiding walks.
• Efficient implementation of the Pivot algorithm for self-avoiding walks
• Self-avoiding walk in five or more dimensions. I: The critical behaviour
• The pivot algorithm: a highly efficient Monte Carlo method for the self-avoiding walk.

Cited in

(20)

• A faster implementation of the pivot algorithm for self-avoiding walks
• The pivot algorithm: a highly efficient Monte Carlo method for the self-avoiding walk.
• The fixed irreducible bridge ensemble for self-avoiding walks
• Monte Carlo methods for the self-avoiding walk
• Stochastic enumeration method for counting NP-hard problems
• Cut-and-permute algorithm for self-avoiding walks in the presence of surfaces
• Accelerating polymer simulation by means of tree data-structures and a parsimonious Metropolis algorithm
• Scale-free Monte Carlo method for calculating the critical exponent \(\gamma\) of self-avoiding walks
• Transforming fixed-length self-avoiding walks into radial \(\text{SLE}_{8/3}\)
• Simulating self-avoiding walks in bounded domains
• Self-avoiding walks in a rectangle
• Conformal invariance predictions for the three-dimensional self-avoiding walk
• Efficient implementation of the Pivot algorithm for self-avoiding walks
• The self-avoiding walk spanning a strip
• The pivot algorithm and polygons: results on the FCC lattice
• Efficient algorithm for computing exact partition functions of lattice polymer models
• Self-testing algorithms for self-avoiding walks
• Monte Carlo study of four-dimensional self-avoiding walks of up to one billion steps
• The SIAM 100-Digit Challenge: a decade later. Inspirations, ramifications, and other eddies left in its wake
• Fast algorithms for computing self-avoiding walks and mesh intersections over unstructured meshes

This page was built for publication: Efficient implementation of the Pivot algorithm for self-avoiding walks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5961852)