Counting polyominoes: A parallel implementation for cluster computing

Iwan Jensen

doi:10.1007/3-540-44863-2_21

Counting polyominoes: A parallel implementation for cluster computing

Iwan Jensen

Research output: Contribution to journal › Article › peer-review

55 Citations (Scopus)

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 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.

Original language	English
Pages (from-to)	203-212
Number of pages	10
Journal	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2659
DOIs	https://doi.org/10.1007/3-540-44863-2_21
Publication status	Published - 18 Jun 2003
Externally published	Yes

Access to Document

10.1007/3-540-44863-2_21Licence: In Copyright

Cite this

@article{76f1d893c2b74d4daa3bf2e0723cc731,

title = "Counting polyominoes: A parallel implementation for cluster computing",

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 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.",

author = "Iwan Jensen",

year = "2003",

month = jun,

day = "18",

doi = "10.1007/3-540-44863-2_21",

language = "English",

volume = "2659",

pages = "203--212",

journal = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

issn = "0302-9743",

publisher = "Springer Nature Switzerland AG",

}

TY - JOUR

T1 - Counting polyominoes

T2 - A parallel implementation for cluster computing

AU - Jensen, Iwan

PY - 2003/6/18

Y1 - 2003/6/18

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=21144443625&partnerID=8YFLogxK

U2 - 10.1007/3-540-44863-2_21

DO - 10.1007/3-540-44863-2_21

M3 - Article

AN - SCOPUS:21144443625

SN - 0302-9743

VL - 2659

SP - 203

EP - 212

JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

ER -

Counting polyominoes: A parallel implementation for cluster computing

Abstract

Access to Document

Other files and links

Fingerprint

Cite this