Exact

It is possible to obtain exact results of the critical site occupation probability for small lattices. This is a matter of enumerating all possible patterns of site occupation to obtain the complete micro-canonical ensemble (then evaluating p_c as described in the method section).

The problem is, as with all percolation simulations, keeping track of clusters and detecting spanning. We could apply the Newman-Ziff algorithm naïvely by building up each state sequentially, testing for spanning clusters, then starting from scratch with the next state. Instead a modified algorithm was used in an attempt at better efficiency.

Since the Newman-Ziff algorithm relies on sequential occupation of sites, it would be nice to enumerate states in that order as much as possible. One example of this for a 2x2 lattice is shown below, where each column is sequential and can be handled as usual by the algorithm. The faded states are repeats and so should be ignored.

There is no obvious way to get such an ordering for larger lattices. However we could divide the lattice into these 2x2 blocks and recursively enumerate these states (that is, for each state of the first block, look at all states of the second, and for each of those all of the third, etc). For this to work with the Newman-Ziff algorithm it must be modified to allow backtracking: the capacity to undo a sequence of site occupations. This is fairly straightforward but requires that

• we maintain a stack (of size N) of which sites have been occupied;
• roots of clusters that have merged to maintain a record of their rank (the number of sites pointing to them). So the rank matrix must be stored separately from the pointer matrix;
• path compresssion does not occur. This weakens the algorithm to an asymptotic running time of O(NlogN).

We can then order the above states more efficiently by avoiding repetition, as shown in the following image.

Crucially, the sequence returns to the initial (empty) state, so we can exhaust all states recursively using these 2x2 blocks. If the lattice length L is odd, 2x1 blocks with a suitable enumeration are used on the edges, and a 1x1 block for the last site.

The code was verified by observing changes in lattice state, step by step. An example of this is here (in this having a random order of occupation, as in Monte-Carlo section).

No previous exact results were available for periodic boundary conditions as used here. However, in the case of a 2x2 lattice it makes no difference. Evaluating p at R_L(p) = 0.5 gives 0.5411961, which matches the exact value given in Ziff & Newman (2002).

Results from running the exact algorithm on lattice sizes up to 6x6 are given in the table above. As expected the time scales exponentially with lattice size: CPU time (secs) ~= 2.5e-7 x 2^N. Extrapolating this to the 7x7 case, it would take roughly 4.5 years. Comparing the 5x5 case with other students' direct implementations, this backtracking method is 9 -- 50 times faster.

Certainly this method could be parallelised: for example, each of 16 processors could handle enumerations under one of the 16 states of the first 2x2 block. However, reducing by a constant factor doesn't help very much with a problem that scales as O(2^N).