{
  "id": "1005.1444",
  "version": "v1",
  "published": "2010-05-10T04:15:40.000Z",
  "updated": "2010-05-10T04:15:40.000Z",
  "title": "Efficient implementation of the pivot algorithm for self-avoiding walks",
  "authors": [
    "Nathan Clisby"
  ],
  "comment": "35 pages, 24 figures, 4 tables. Accepted for publication in the Journal of Statistical Physics.",
  "categories": [
    "cond-mat.stat-mech",
    "math-ph",
    "math.MP",
    "physics.chem-ph",
    "physics.comp-ph"
  ],
  "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2010-05-10T04:15:40.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "pivot algorithm",
      "efficient implementation",
      "simple cubic lattice",
      "mean time",
      "step self-avoiding walks"
    ],
    "tags": [
      "journal article"
    ],
    "publication": {
      "doi": "10.1007/s10955-010-9994-8",
      "journal": "Journal of Statistical Physics",
      "year": 2010,
      "month": "Jul",
      "volume": 140,
      "number": 2,
      "pages": 349
    },
    "note": {
      "typesetting": "TeX",
      "pages": 35,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010JSP...140..349C"
    }
  }
}