A distributed system for enumerating main classes of sets of orthogonal Latin squares

[摘要] ENGLISH ABSTRACT: A Latin square is an n n array containing n copies of each of n distinct symbols in such a waythat no symbol is repeated in any row or column. Two Latin squares are orthogonal if, whensuperimposed, the ordered pairs in the n2 cells are all distinct. This notion of orthogonality extendsnaturally to sets of k > 2 mutually orthogonal Latin squares (abbreviated in the literatureas k-MOLS), whichnd application in scheduling problems and coding theory.In these instances it is important to di erentiate between structurally di erent k-MOLS. It isthus useful to classify Latin squares and k-MOLS into equivalence classes according to theirstructural properties | this thesis is concerned speci cally with main classes of k-MOLS, oneof the largest equivalence classes of sets of Latin squares.The number of main classes of k-MOLS of orders 3 n 8 have been enumerated in theliterature by recursive backtracking algorithms. All enumeration attempts for k-MOLS of ordern > 8 have, however, encountered a computational barrier using current computing technologyin traditional computing paradigms. In this thesis, the feasibility of these enumerations of ordern > 8 is analysed and a potential way of overcoming this computational barrier is proposed.A backtracking enumeration algorithm from the literature is implemented and validated, afterwhich novel estimates of the sizes of the enumeration search trees for k-MOLS of orders n > 8produced by this backtracking algorithm are presented.It is also advocated that the above-mentioned computational barrier may be overcome by volunteercomputing, a computing paradigm in which large computations are distributed overthousands or even millions of volunteered computing devices, such as desktop computers andAndroid cellphones. A volunteer computing project is designed for the distributed enumerationof main classes of k-MOLS. Initial test results obtained from this volunteer computing projecthave called for a novel work unit issuing policy which allows the participating host resources tobe utilised e ectively during enumerations of main classes of k-MOLS of arbitrary orders.A local pilot study involving the enumeration of main classes of 3-MOLS of order 8 has con rmedthe feasibility of adopting the volunteer computing project as an avenue of approach towardsthe enumeration of k-MOLS of orders n > 8 and preliminary results of an ongoing enumerationattempt for the main classes of 7-MOLS of order 9 are presented.

[发布机构] Stellenbosch University