Journal article
Efficient Implementation of the Pivot Algorithm for Self-avoiding Walks
Nathan Clisby
JOURNAL OF STATISTICAL PHYSICS | SPRINGER | Published : 2010
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 t..
View full abstractGrants
Funding Acknowledgements
I thank Ian Enting, Tony Guttmann, Gordon Slade, Alan Sokal, and two anonymous referees for useful comments on the manuscript. I would also like to thank an anonymous referee for comments on an earlier version of this article which led to deeper consideration of the algorithmic complexity of Shuffle_intersect. I am grateful to Tom Kennedy for releasing his implementation of the pivot algorithm under the GNU GPLv2 licence. Computations were performed using the resources of the Victorian Partnership for Advanced Computing (VPAC). Financial support from the Australian Research Council is gratefully acknowledged.