2003 Counting polyominoes: a parallel implementation for cluster computing Computational Science— ICCS 2003 ed P

Abstract. 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 enu-meration of polyominoes, which are connected sets of lattice cells joined at an edge. The algorithm implements the finite-lattice method and as-sociated 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.