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).
Representing Boundaries
as Motzkin Paths
Polyomino boundaries and Motzkin paths.
B CC AA A A A A A - - - - - -
code
0
2
3
1
9 12 16 2 3 4 5 8 10 11 13 14 15 7 6 1
Motzkin path
9 12 16 2 3 4 5 8 10 11 13 14 15 7 6 1 0 17