A distributed system for enumerating main classes of sets of orthogonal Latin squares
Date
2014-12
Authors
Benade, Johannes Gerhardus
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH ABSTRACT: A Latin square is an n n array containing n copies of each of n distinct symbols in such a way
that no symbol is repeated in any row or column. Two Latin squares are orthogonal if, when
superimposed, the ordered pairs in the n2 cells are all distinct. This notion of orthogonality extends
naturally to sets of k > 2 mutually orthogonal Latin squares (abbreviated in the literature
as k-MOLS), which nd application in scheduling problems and coding theory.
In these instances it is important to di erentiate between structurally di erent k-MOLS. It is
thus useful to classify Latin squares and k-MOLS into equivalence classes according to their
structural properties | this thesis is concerned speci cally with main classes of k-MOLS, one
of 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 the
literature by recursive backtracking algorithms. All enumeration attempts for k-MOLS of order
n > 8 have, however, encountered a computational barrier using current computing technology
in traditional computing paradigms. In this thesis, the feasibility of these enumerations of order
n > 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, after
which novel estimates of the sizes of the enumeration search trees for k-MOLS of orders n > 8
produced by this backtracking algorithm are presented.
It is also advocated that the above-mentioned computational barrier may be overcome by volunteer
computing, a computing paradigm in which large computations are distributed over
thousands or even millions of volunteered computing devices, such as desktop computers and
Android cellphones. A volunteer computing project is designed for the distributed enumeration
of main classes of k-MOLS. Initial test results obtained from this volunteer computing project
have called for a novel work unit issuing policy which allows the participating host resources to
be 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 rmed
the feasibility of adopting the volunteer computing project as an avenue of approach towards
the enumeration of k-MOLS of orders n > 8 and preliminary results of an ongoing enumeration
attempt for the main classes of 7-MOLS of order 9 are presented.
AFRIKAANSE OPSOMMING: 'n Latynse vierkant is 'n n n skikking wat n kopie e van elk van n verskillende simbole bevat sodat geen simbool in enige ry of kolom daarvan herhaal word nie. Indien twee Latynse vierkante op mekaar gesuperponeer word, en die geordende pare simbole wat sodoende in die n2 selle gevorm word, almal verskillend is, word die vierkante ortogonaal genoem. Die begrip van ortogonaliteit veralgemeen op 'n natuurlike wyse na k > 2 onderling ortogonale Latynse vierkante (wat in die internasionale literatuur as k-MOLS afgekort word) en vind toepassing in skeduleringsprobleme en kodeerteorie. In hierdie toepassings is dit belangrik om 'n onderskeid te tref tussen struktureel verskillende k- MOLS. Dit is gevolglik nuttig om Latynse vierkante en k-MOLS in ekwivalensieklasse volgens hul strukturele eienskappe te klassi seer. In hierdie verhandeling word daar gefokus op hoofklasse van k-MOLS, een van die grootste ekwivalensieklasse van versamelings Latynse vierkante. Die getal hoofklasse van k-MOLS van ordes 3 n 8 is in die literatuur deur middel van rekursiewe algoritmes met terugkering getel. Geen poging om hoofklasse van k-MOLS van ordes n > 8 te tel, kon egter daarin slaag om 'n berekeningstruikelblok te oorkom wat as gevolg van huidige rekentegnologiese beperkings bestaan nie. In hierdie verhandeling word die haalbaarheid van sulke telpogings vir orde n > 8 ondersoek en word 'n metode voorgestel waarmee hierdie berekeningstruikelblok moontlik oorkom kan word. 'n Bestaande telalgoritme met terugkering word ge mplementeer en gevalideer, waarna nuwe afskattings van die groottes van die soekbome vir hoofklasse van k-MOLS van ordes n > 8 wat deur hierdie algoritme deurstap moet word, daargestel word. Daar word geargumenteer dat die bogenoemde berekeningstruikelblok moontlik oorkom kan word deur gebruik te maak van 'n grootskaalse parallelle rekenparadigma waarin groot berekeninge oor duisende of selfs miljoene rekentoestelle, soos tafelrekenaars of Android sellul^ere telefone wat vrywillig deur gebruikers vir hierdie doel beskikbaar gemaak word. So 'n verspreide berekeningsprojek word vir hoofklasse van k-MOLS ontwerp. Aanvanklike resultate wat uit hierdie projek voortgespruit het, het 'n nuwe beleid genoodsaak waarvolgens werkeenhede aan deelnemende rekentoestelle op s o 'n wyse uitgedeel word dat die projek doeltre end van hulpbronne gebruik maak, selfs wanneer hoofklasse van k-MOLS van arbitr^ere ordes bepaal word. 'n Lokale proefstudie word geloods waartydens bekende telresultate vir hoofklasse van k-MOLS van orde 8 bevestig word. Die haalbaarheid van 'n verspreide berekeningsbenadering, waaraan baie vrywilligers kan deelneem om hoofklasse van k-MOLS van orde n > 8 te tel, word ondersoek en die resultate van 'n huidige verspreide berekeningspoging om hoofklasse van 7-MOLS van orde 9 te tel, word gerapporteer.
AFRIKAANSE OPSOMMING: 'n Latynse vierkant is 'n n n skikking wat n kopie e van elk van n verskillende simbole bevat sodat geen simbool in enige ry of kolom daarvan herhaal word nie. Indien twee Latynse vierkante op mekaar gesuperponeer word, en die geordende pare simbole wat sodoende in die n2 selle gevorm word, almal verskillend is, word die vierkante ortogonaal genoem. Die begrip van ortogonaliteit veralgemeen op 'n natuurlike wyse na k > 2 onderling ortogonale Latynse vierkante (wat in die internasionale literatuur as k-MOLS afgekort word) en vind toepassing in skeduleringsprobleme en kodeerteorie. In hierdie toepassings is dit belangrik om 'n onderskeid te tref tussen struktureel verskillende k- MOLS. Dit is gevolglik nuttig om Latynse vierkante en k-MOLS in ekwivalensieklasse volgens hul strukturele eienskappe te klassi seer. In hierdie verhandeling word daar gefokus op hoofklasse van k-MOLS, een van die grootste ekwivalensieklasse van versamelings Latynse vierkante. Die getal hoofklasse van k-MOLS van ordes 3 n 8 is in die literatuur deur middel van rekursiewe algoritmes met terugkering getel. Geen poging om hoofklasse van k-MOLS van ordes n > 8 te tel, kon egter daarin slaag om 'n berekeningstruikelblok te oorkom wat as gevolg van huidige rekentegnologiese beperkings bestaan nie. In hierdie verhandeling word die haalbaarheid van sulke telpogings vir orde n > 8 ondersoek en word 'n metode voorgestel waarmee hierdie berekeningstruikelblok moontlik oorkom kan word. 'n Bestaande telalgoritme met terugkering word ge mplementeer en gevalideer, waarna nuwe afskattings van die groottes van die soekbome vir hoofklasse van k-MOLS van ordes n > 8 wat deur hierdie algoritme deurstap moet word, daargestel word. Daar word geargumenteer dat die bogenoemde berekeningstruikelblok moontlik oorkom kan word deur gebruik te maak van 'n grootskaalse parallelle rekenparadigma waarin groot berekeninge oor duisende of selfs miljoene rekentoestelle, soos tafelrekenaars of Android sellul^ere telefone wat vrywillig deur gebruikers vir hierdie doel beskikbaar gemaak word. So 'n verspreide berekeningsprojek word vir hoofklasse van k-MOLS ontwerp. Aanvanklike resultate wat uit hierdie projek voortgespruit het, het 'n nuwe beleid genoodsaak waarvolgens werkeenhede aan deelnemende rekentoestelle op s o 'n wyse uitgedeel word dat die projek doeltre end van hulpbronne gebruik maak, selfs wanneer hoofklasse van k-MOLS van arbitr^ere ordes bepaal word. 'n Lokale proefstudie word geloods waartydens bekende telresultate vir hoofklasse van k-MOLS van orde 8 bevestig word. Die haalbaarheid van 'n verspreide berekeningsbenadering, waaraan baie vrywilligers kan deelneem om hoofklasse van k-MOLS van orde n > 8 te tel, word ondersoek en die resultate van 'n huidige verspreide berekeningspoging om hoofklasse van 7-MOLS van orde 9 te tel, word gerapporteer.
Description
Thesis (MSc)--Stellenbosch University, 2014.
Keywords
UCTD, Dissertations -- Logistics, Theses -- Logistics, Magic squares