SAWdoubler for counting self-avoiding walks

SAWdoubler

SAWdoubler is a software package for counting the number of self-avoiding walks on a regular lattice, based on the length-doubling method described in: Exact enumeration of self-avoiding walks by Raoul D. Schram, Gerard T. Barkema, and Rob H. Bisseling Journal of Statistical Mechanics: Theory and Experiment (2011) p06019.

The aim of the package is to enable counting self-avoiding walks on a variety of lattices, and stimulate research into this topic. Please feel free to explore the possibilities of modifying this program. Have fun!

The package includes three example lattices: the 3D simple cubic (SC) lattice, the BCC lattice, and the FCC lattice. All functions related to the specific lattice are included in one file (e.g. lattice_sc.c) and all functions related to the counting procedure in another (sawdoubler.c). Furthermore there are files that capture common symmetries of the lattices. This way, it is easy to modify the lattice without touching the counting functions and data structures.

New features of version 2.0.1

This is a small bug fix release to make installation smoother. Thanks to Keith Briggs (Oxford) for helpful comments.
• Removed invisible, superfluous files that cause tar error messages.
• Reduced the default value of MAXNODES in saw.h, to enable running on computers with less memory.
• Print a more helpful error message in case not enough memory is available.

New features of version 2.0, released March 28, 2017

• The number of walks Z_N can now be determined for every integer N, in particular odd N. The length-doubling method computes Z_(N+M) for every pair of integers N, M >= 1.
• The squared end-to-end distance P_N is also computed, defined as the sum of the squared Euclidean distances of the endpoints of all the self-avoiding walks.
• New lattices have been added to the simple cubic (SC) lattice: Body-Centred Cubic (BCC), Face-Centred Cubic (FCC).
• A parallel version is included based on the MulticoreBSP library for easy shared memory parallel programming.

Related papers

The length-doubling method has been published in Exact enumeration of self-avoiding walks by Raoul D. Schram, Gerard T. Barkema, and Rob H. Bisseling Journal of Statistical Mechanics: Theory and Experiment (2011) p06019.

The paper accompanying the SAWdoubler software, explaining the algorithm and its implementation, and also presenting timing experiments and discussing memory use is SAWdoubler: a program for counting self-avoiding walks by Raoul D. Schram, Gerard T. Barkema, and Rob H. Bisseling, Computer Physics Communications, 184 (2013) pp. 891-898.

Results on the BCC and FCC lattice are obtained and analysed in Exact enumeration of self-avoiding walks on BCC and FCC lattices by Raoul D. Schram, Gerard T. Barkema, Rob H. Bisseling, and Nathan Clisby, arXiv:1703.09340 [cond-mat.stat-mech] March 27, 2017.

Selected related lectures

• Self-avoiding walks by Rob Bisseling, joint work with Raoul Schram and Gerard Barkema, Lecture given at Mathematics colloquium, Utrecht April 19, 2012.

This software is copyrighted (version 1, 2012; version 2, 2017) by Raoul Schram, Rob Bisseling, Gerard Barkema. You can use and modify it under the GNU Lesser General Public License, see GNU Licenses. Also see the files, README, COPYING, COPYING.LESSER. Anything free, as usual, comes with no guarantee!

Contributions

Other contributions are welcome!

Errata and known issues

• Erratum: line 33 of Algorithm 2 of SAWdoubler: a program for counting self-avoiding walks contains an error:
the statement Z <-- Z + count[v]^2 should be replaced by sum <-- sum + count[v]. Here, sum=0 should be initialised before the loop of line 32, and sum^2 should be added to Z after the loop. In the program SAWdoubler this was done correctly. Also all obtained results are correct. Error found by Sarita de Berg (May 2017).

Previous versions

Download the first version of the SAWdoubler software, version 1.0 (tar gzipped), released August 15, 2012.

Last updated July 12, 2017.