Efficient implementation of the Pivot algorithm for self-avoiding walks

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

Nathan Clisby

Publication date: 16 September 2010

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

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.

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)

Cites Work

• Self-avoiding walk in five or more dimensions. I: The critical behaviour
• Cache-Oblivious Algorithms
• Title not available (Why is that?)
• Title not available (Why is that?)
• Efficient implementation of the Pivot algorithm for self-avoiding walks
• The pivot algorithm: a highly efficient Monte Carlo method for the self-avoiding walk.
• Title not available (Why is that?)
• Critical exponents, hyperscaling, and universal amplitude ratios for two- and three-dimensional self-avoiding walks.
• Correction-to-scaling exponents for two-dimensional self-avoiding walks
• A faster implementation of the pivot algorithm for self-avoiding walks
• Title not available (Why is that?)

Cited In (17)

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

   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 👍 👎

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)