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 the lattice or in the continuum, and hence promises to be widely useful.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alexandrowicz, Z.: Monte Carlo of chains with excluded volume: a way to evade sample attrition. J. Chem. Phys. 51, 561–565 (1969)
Baiesi, M., Orlandini, E., Stella, A.L.: Peculiar scaling of self-avoiding walk contacts. Phys. Rev. Lett. 87, 070602 (2001)
Caracciolo, S., Guttmann, A.J., Jensen, I., Pelissetto, A., Rogers, A.N., Sokal, A.D.: Correction-to-scaling exponents for two-dimensional self-avoiding walks. J. Stat. Phys. 120, 1037–1100 (2005)
Clisby, N.: Accurate estimate of the critical exponent ν for self-avoiding walks via a fast implementation of the pivot algorithm. Phys. Rev. Lett. 104, 055702 (2010)
Frigo, M., Leiserson, C.E., Prokop, H., Ramachandran, S.: Cache oblivious algorithms. In: Proceedings 40th Annual Symposium on Foundations of Computer Science, pp. 285–297 (1999)
Gabay, M., Garel, T.: Renormalization along the chemical sequence of a single polymer chain. J. Phys. Lett. 39, 123–125 (1978)
Guttman, A.: R-trees: A dynamic index structure for spatial searching. In: Yormark, B. (ed.) SIGMOD ’84, pp. 47–57. ACM, New York (1984)
Hara, T., Slade, G.: Self-avoiding walk in five or more dimensions I. The critical behaviour. Commun. Math. Phys. 147, 101–136 (1992)
Kennedy, T.: A faster implementation of the pivot algorithm for self-avoiding walks. J. Stat. Phys. 106, 407–429 (2002)
Klosowski, J.T., Held, M., Mitchell, J.S.B., Sowizral, H., Zikan, K.: Efficient collision detection using bounding volume hierarchies of k-dops. IEEE T. Vis. Comput. Gr. 4, 21–36 (1998)
Kremer, K., Baumgärtner, A., Binder, K.: Monte Carlo renormalization of hard sphere polymer chains in two to five dimensions. Z. Phys. B, Condens. Matt. 40, 331–341 (1981)
Kumar, P.: Cache Oblivious Algorithms, pp. 193–212. Springer, Berlin (2003). Chap. 9
Lal, M.: ‘Monte Carlo’ computer simulation of chain molecules. I. Mol. Phys. 17, 57–64 (1969)
Lawler, G.F., Schramm, O., Werner, W.: On the scaling limit of planar self-avoiding walk. In: Fractal Geometry and Applications: a Jubilee of Benoit Mandelbrot, Part 2. Proc. Sympos. Pure Math., vol. 72, pp. 339–364. Am. Math. Soc., Providence (2004)
Li, B., Madras, N., Sokal, A.D.: Critical exponents, hyperscaling, and universal amplitude ratios for two- and three-dimensional self-avoiding walks. J. Stat. Phys. 80, 661–754 (1995)
Madras, N., Slade, G.: The Self-Avoiding Walk. Birkhaüser, Boston (1993)
Madras, N., Sokal, A.D.: The pivot algorithm: A highly efficient Monte Carlo method for the self-avoiding walk. J. Stat. Phys. 50, 109–186 (1988)
Müller, S., Schäfer, L.: On the number of intersections of self-repelling polymer chains. Eur. Phys. J. B 2, 351–369 (1998)
Nienhuis, B.: Exact critical point and critical exponents of O(n) models in two dimensions. Phys. Rev. Lett. 49, 1062–1065 (1982)
Oono, Y.: Renormalization along the polymer chain. J. Phys. Soc. Jpn. 47, 683–684 (1979)
Sedgewick, R.: Algorithms in C, Parts 1–4, 3rd edn. Addison-Wesley, Reading (1998)
Sokal, A.D.: Monte Carlo methods for the self-avoiding walk. arXiv:hep-lat/9405016 (1994)
Sokal, A.D.: Monte Carlo methods for the self-avoiding walk. Nucl. Phys. B (Proc. Suppl.) 47, 172–179 (1996)
van Emde Boas, P.: Preserving order in a forest in less than logarithmic time. In: Proceedings 16th Annual Symposium on Foundations of Computer Science, pp. 75–84 (1975)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Clisby, N. Efficient Implementation of the Pivot Algorithm for Self-avoiding Walks. J Stat Phys 140, 349–392 (2010). https://doi.org/10.1007/s10955-010-9994-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10955-010-9994-8