SAWdoubler: A program for counting self-avoiding walks

doi:10.1016/j.cpc.2012.10.026

SAWdoubler: A program for counting self-avoiding walks

2013-03-01

11

OA

AI

DOI：10.1016/j.cpc.2012.10.026

原文链接

查看原文

摘要

En 中文

This article presents SAWdoubler, a package for counting the total number Z(N) of self-avoiding walks (SAWs) on a regular lattice by the length-doubling method, of which the basic concept has been published previously by us. We discuss an algorithm for the creation of all SAWs of length N, efficient storage of these SAWs in a tree data structure, and an algorithm for the computation of correction terms to the count Z(2N) for SAWs of double length, removing all combinations of two intersecting single-length SAWs. We present an efficient numbering of the lattice sites that enables exploitation of symmetry and leads to a smaller tree data structure; this numbering is by increasing Euclidean distance from the origin of the lattice. Furthermore, we show how the computation can be parallelised by distributing the iterations of the main loop of the algorithm over the cores of a multicore architecture. Experimental results on the 3D cubic lattice demonstrate that Z(28) can be computed on a dual-core PC in only 1 h and 40 min, with a speedup of 1.56 compared to the single-core computation and with a gain by using symmetry of a factor of 26. We present results for memory use and show how the computation is made to fit in 4 GB RAM. It is easy to extend the SAWdoubler software to other lattices; it is publicly available under the GNU LGPL license. Program summary Program title: SAWdoubler Catalogue identifier: AEOB_v1_0 Program summary URL: http://cpc.cs.qub.ac.uk/summaries/AEOB_v1_0.html Program obtainable from: CPC Program Library, Queen's University, Belfast, N. Ireland Licensing provisions: GNU Lesser General Public Licence No. of lines in distributed program, including test data, etc.: 2101 No. of bytes in distributed program, including test data, etc.: 19816 Distribution format: tar.gz Programming language: C. Computer: Any computer with a UNIX-like operating system and a C compiler. For large problems, use is made of specific 128-bit integer arithmetic provided by the gcc compiler. Operating system: Any UNIX-like system; developed under Linux and Mac OS 10. Has the code been vectorised or parallelised?: Yes. A parallel version of the code is available in the Extras directory of the distribution file. RAM: Problem dependent (2 GB for counting SAWs of length 28 on the 3D cubic lattice) Classification: 16.11. Nature of problem: Computing the number of self-avoiding walks of a given length on a given lattice. Solution method: Length-doubling. Restrictions: The length of the walk must be even. Lattice is 3D simple cubic. Additional comments: The lattice can be replaced by other lattices, such as BCC, FCC, or a 2D square lattice. Running time: Problem dependent (2.5 h using one processor core for length 28 on the 3D cubic lattice). (c) 2012 Elsevier B.V. All rights reserved.

Keyword:

Self-avoiding walk

Enumeration

Simple cubic lattice

SAWdoubler: A program for counting self-avoiding walks

摘要

AI总结

期刊

机构

引用论文