Efficient implementation of the Pivot algorithm for self-avoiding walks

DOI10.1007/S10955-010-9994-8MaRDI QIDQ5961852zbMATH OpenOpenAlexFDO

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 Carlopivot algorithmpolymerself-avoiding walk

Mathematics Subject Classification ID

Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics (82B41) 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

• 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
• 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?)
• 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

(23)

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

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)