Efficient Implementation of the Pivot Algorithm for Self-avoiding Walks
Efficient Implementation of the Pivot Algorithm for Self-avoiding Walks
复制标题
自回避行走枢轴算法的高效实现
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
N. Clisby
中科院分区：
文献类型：
--
作者：
N. Clisby
用于自避免行走的枢轴算法已经以比以前的实现快得多的方式实现，从而能够有效地模拟极长的行走。我们明确地描述了所使用的数据结构和算法，并提供了一个启发式的论点，每尝试枢轴N步自避免行走的平均时间是O（1）的正方形和简单的立方格。数值实验进行了自我避免行走高达2.68亿步是一致的O（log N）的行为的正方形晶格和O（log N）的行为的简单立方晶格。我们的方法可以适用于其他模型的聚合物与短程相互作用，在晶格上或在连续，因此有望被广泛使用。
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.