Communications of the ACM

cause any problem because succ0[s], if it is non-null, is always less than s. There are thus no circular references, and each entry is set before it is used. In fact, the states can be partitioned into groups G1, G2, … , GW; the group Gi contains the states corresponding to boundaries in which i is the smallest index of an occupied cell, or the boundaries that start with i − 1 empty cells. The dependence between the entries of the groups is shown schematically in Figure 5; succ0[s] of an entrys ∈ Gi (for 1 ≤ i ≤ W − 1), if it is non-null, belongs to Gi+ 1.

At the end, ynew is moved to yold to
start the new iteration. In the itera-
tion (∗), the new vector ynew is a linear
function of the old vector yold and, as
already indicated, can be written as a
linear transformation yold := Qyold. The
nonnegative integer matrix Q is im-
plicitly given through the iteration (∗).
We are interested in the growth rate of
the sequence of vectors yold that is de-
termined by the dominant eigenvalue
λ W of Q. It is not difficult to show5 that
after every iteration, λ W is contained in
the interval
mins ynew[s]
yold[s]
≤ λw ≤ maxs ynew[s]
. ( 1)

By the Perron-Frobenius Theorem about the eigenvalues of nonnegative matrices, the two bounds converge to λ W, and yold converges to a corresponding eigenvector.

As written, the program calculates the exact number of polyominoes of each size and state, provided the computations are carried out with precise integer arithmetic. However, these numbers grow like (λw)n, and the program can thus not afford to store them exactly. Instead, we use single-precision floating-point numbers for yold and ynew. Even so, the program must rescale the vector yold from time to time in order to prevent floating-point overflow: Whenever the largest entry exceeds 280 at the end of an iteration, the program divides the whole vector by 2100. This rescaling does not affect the convergence of the process. The program terminates when the two bounds are close enough. The left-hand side of ( 1) is a lower bound on λ W, which in turn is a lower bound on λ, and this is our real goal.

Sequential Runs

In 2004, we obtained good approximations of yold up to W = 22. The program required quite a bit of main memory (RAM) by the standards of the time. The computation of λ22 ≈

3.9801 took approximately six hours on a single-processor machine with 32GB of RAM. (Today, the same program runs in 20 minutes on a regular workstation.) By extrapolating the first 22 values of the sequence λ W

The figure here illustrates the representation of polyomino boundaries as Motzkin paths. The bottom part of the figure shows a partially constructed polyomino on a twisted cylinder of width 16. The dashed line indicates two adjacent cells that are connected “around the cylinder,” where such a connection is not immediately apparent. The boundary cells (top row) are shown in darker gray. The light-gray cells away from the boundary need not be recorded individually; what matters is the connectivity among the boundary cells they provide. This connectivity is indicated in a symbolic code -AAA-B-CC-AA--AA. Boundary cells in the same component are represented by the same letter, and the character '-' denotes an empty cell. However, we did not use this code in our program. Instead, we represented a boundary as a Motzkin path, as shown in the top part of the figure, because this representation allows for a convenient bijection to successive integers and thus for a compact storage of the boundary in a vector. Intuitively, the Motzkin path follows the movements of a stack when reading the code from left to right. Whenever a new component starts (such as component A in position 2 or component B in position 6), the path moves up.

Whenever a component is temporarily interrupted (such as component A in position

5), the path also moves up. The path moves down when an interrupted component is resumed (such as component A in positions 11 and 15) or when a component is completed (positions 7, 10, and 17). The crucial property is that components cannot cross; that is, a pattern like ..A..B..A..B.. cannot occur. As a consequence of these rules, the occupied cells correspond to odd levels in the path, and the free cells correspond to even levels. The correspondence between boundaries and Motzkin paths was pointed out by Stefan Felsner of the Technische Universität Berlin (private communication).