Exact Enumerations in Statistical Mechanics and Combinatorics

Significant Achievements, Anticipated Outcomes and Future Work

In collaboration with C Richard and A J Guttmann we have conjectured the exact scaling function for self-avoiding polygons. The theoretical predictions were confirmed by high quality numerical calculations based on extensive series expansions in which the APAC National Facility played a crucial role. This work is continuing in order to further investigate the properties of scaling functions for polygon model. In collaboration with A J Guttmann we have recently been able to find, starting from very long series expansions, differential equations satisfied by the generating functions of several simple lattice models.

Lattice animals are of great inherent interest in combinatorics and statistical mechanics both in their own right and also due a close relationship to percolation. We have enumerated lattice animals up to size 56 on the square lattice. We have developed a very efficient parallel version of the algorithm for this problem. We have extended this investigation to the hexagonal and triangular lattices, and are currently extending it to bond animals as well.

Percolation is one of the fundamental problems in statistical mechanics and is of great theoretical interest in its own right as well as being applicable to a wide variety of problems in physics, biology and many other areas of science. Percolation is commonly formulated as a problem on a lattice in which the edges and/or vertices are occupied (vacant) with probability p (1-p). In collaboration with Prof. R M. Ziff we study universal amplitude ratios and scaling functions in percolation problems. This involves the calculation of perimeter polynomials for bond and site percolation on the square, hexagonal and triangular lattices to high order.

We have developed algorithms for self-avoiding walks (a model relevant to polymer science) on various lattices. We have significantly extended the series for the square, triangular and honeycomb lattices including series for properties such as the end-to-end distance and radius of gyration. We are currently extending this work in order to calculate the full end-point distribution of the square lattice. Of considerable interest are some directed lattices where theoretical work has predicted a small change in the behaviour observed on usual lattices. In addition we plan to derive series for walks attached to a surface or constrained to a wedge. We also plan to extend this work to interacting SAWs which will include several simple models relevant to the stretching of DNA or other long polymers.

Computational Techniques Used

Generally the calculation of a series expansion is a problem in which the time (and memory) required to calculate N terms grows exponentially with N. We use the finite-lattice method (FLM) to calculate series expansions. The basic idea of the FLM is to calculate the first terms in the expansion by combining results for the same problem but restricted to small finite lattices, such as rectangles on the square lattice.

The algorithms we use to calculate results on the finite lattices are iterative in nature and based on so-called transfer matrix (TM) techniques. The transfer matrix technique involves drawing a boundary through the lattice intersecting a set of edges. This boundary is moved so as to add one site at a time to the finite lattice while updating a weight assigned to each configuration.

As an example we mention the enumeration of polygons on the square lattice. A polygon can be seen as a walk along the edges of a lattice which returns to the starting point but has no other self-intersections. We are interested in counting the number of polygons of according to the perimeter length and/or enclosed area. The calculation up to some maximal perimeter or area can be done by counting the number of polygons spanning rectangles of length l and width w. Due to the symmetry of the square lattice we need only consider rectangles with l>=w. Any polygons spanning such a rectangle has perimeter at least 2(w+l)-4. By adding the contributions from all rectangles of width w<=W and length w<=l<2W-w+1, with contributions from rectangles with l>w counted twice, the number of polygons per vertex of an infinite lattice is obtained correctly up to perimeter 4W-2.

The contribution from individual rectangles is done using transfer matrix (TM) techniques. In applying the TM technique to the enumeration of polygons we regard them as sets of bonds on the finite lattice with the properties:

1. A weight x is associated with each bond.
2. All vertices are of degree 0 or 2.
3. Apart from isolated vertices, the graph has a single connected component.
4. Each graph must span the rectangle from left to right and from top to bottom.

The transfer matrix technique involves drawing a boundary line through the rectangle intersecting a set of up to w+1 edges. Polygons in a given rectangle are enumerated by moving the boundary line so as to add one vertex at a time. In this fashion we build up the rectangle column by column with each column built up vertex by vertex. The boundary line intersects partially completed polygons consisting of disjoint loops that must all be connected to form a single polygon. For each configuration of occupied or empty edges along the intersection we maintain a perimeter generating function for open loops to the left of the line cutting the intersection in that particular pattern. The updating of the generating functions depends primarily on the configuration of the two edges at the kink in the boundary line prior to the move. As the boundary line is moved the two new edges intersected by the boundary line can be either empty or occupied. The TM rules for updating the generating functions must be chosen so as to respect the constraints above. The details are to complicated to give here. We will however outline how the parallel version works.

The TM algorithm is eminently suited for the APAC National Facility. The exponential growth in time and memory requirements makes it imperative to have access to very powerful supercomputer facilities. Furthermore, the updating of boundary configurations in the TM algorithm depends only on the local configuration where a new site is being added. It is therefore quite easy to parallelise the TM algorithm. We recently enumerated self-avoiding walks up to length 71. This calculation required a total of more than 100GB of memory and such resources are only available on the APAC National Facility.

One of the main ways of achieving a good parallel algorithm using data decomposition to find a property of the problem which remains invariant under a single iteration and thus splits the data set into disjoint sections which can be updated independently. In this case we have such an invariant since any edge not directly involved in the update cannot change from being empty to being occupied and vice versa. This invariant allows us to parallelise the algorithm in such a way that we can do the calculation completely independently on each processor with just two redistributions of the data set each time an extra column is added to the lattice.

The main points of the algorithm are summarized below:

1. With the boundary line straight (having no kinks) distribute the data across processors so that configurations with the same occupation pattern along the lower half of the boundary line are placed on the same processor.
2. Do the TM update inserting the top-half of a new column. This can be done independently by each processor because the occupation pattern in the lower half remains unchanged.
3. Upon reaching the half-way mark redistribute the data so that configurations with the same occupation pattern along the upper half of the boundary line are placed on the same processor.
4. Do the TM update inserting the bottom-half of a new column.
5. Go back to 1.

Timing of the various parts of the algorithm shows that the typical additional cost of the parallel algorithm is no more than 10%. That is typically no more than 10% of the time is used in the redistribution and inter node communications.

Publications, Awards and External Funding

External Funding and Awards

Iwan Jensen is funded as a Senior Research Fellow by the ARC Centre of Excellence for Mathematics and Statistics of Complex Systems.

Publications

I. Jensen, Low-density series expansions for directed percolation IV. Temporal disorder, Journal of Physics A: Mathematical and General, 38, 2005, 1441-1449.

M. Bousquet-Mélou, A. J. Guttmann and I. Jensen, Self-avoiding walks crossing a square, Journal of Physics A: Mathematical and General, 38, 2005, 9159-9181.

S. Caracciolo, A. J. Guttmann, I. Jensen, A. Pelissetto, A. N. Rogers, and A. D. Sokal, Correction-to-scaling exponents for two-dimensional self-avoiding walks, Journal of Statistical Physics, 120, 2005, 1037-1100.

I. Jensen, Perimeter generating functions for the mean-squared radius of gyration of convex polygons Journal of Physics A: Mathematical and General, 38, 2005, L769-L775.

A. J. Guttmann and I. Jensen, Fuchsian differential equation for the perimeter generating function of three-choice polygons, Séminaire Lotharingien de Combinatoire, 54, 2006, Article B54c (14 pages).

A. J. Guttmann and I. Jensen, The perimeter generating function of punctured staircase polygons, Journal of Physics A: Mathematical and General, 39, 2006, 3871-3882.