Counting Polyominoes: A Parallel Implementation for Cluster Computing

摘要

The exact enumeration of most interesting combinatorial problems has exponential computational complexity. The finite-lattice method reduces this complexity for most two-dimensional problems. The basic idea is to enumerate the problem on small finite lattices using a transfer-matrix formalism. Systematically grow the size of the lattices and combine the results in order to obtain the desired series for the infinite lattice limit. We have developed a parallel algorithm for the enumeration of polyominoes, which are connected sets of lattice cells joined at an edge. The algorithm implements the finite-lattice method and associated transfer-matrix calculations in a very efficient parallel setup. Test runs of the algorithm on a HP server cluster indicates that in this environment the algorithm scales perfectly from 2 to 64 processors.