Computing autotopism groups of partial Latin rectangles: A pilot study. Issue 3 (20th April 2020)

• Record Type: Journal Article
• Authors: Stones, Rebecca J.; Falcón, Raúl M.; Kotlar, Daniel; Marbach, Trent G.
• Is Part Of: Computational and mathematical methods. Volume 3:Issue 3(2021)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2020-04-20
• Subjects: autotopism -- Latin square -- partial Latin rectangle; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Periodicals; Numerical analysis; Mathematics -- Data processing; Periodicals; 004.0151
• DOI: 10.1002/cmm4.1094
• Languages: English
• ISSNs: 2577-7408

Abstract

Abstract : Computing the autotopism group of a partial Latin rectangle can be performed in a variety of ways. This pilot study has two aims: (a) to compare these methods experimentally and (b) to identify the design goals one should have in mind for developing practical software. To this end, we compare six families of algorithms (two backtracking methods and four graph automorphism methods), with and without the use of entry invariants, on two test suites. We consider two entry invariants: one determined by the frequencies of row, column, and symbol representatives, and one determined by 2×2 submatrices. We find: (a) with very few entries, many symmetries often exist, and these should be identified mathematically rather than computationally, (b) with an intermediate number of entries, a quick‐to‐compute entry invariant was effective at reducing the need for computation, (c) with an almost‐full partial Latin rectangle, more sophisticated entry invariants are needed, and (d) the performances for (full) Latin squares and almost‐full partial Latin squares are significantly poorer than other partial Latin rectangles of comparable size, obstructed by the existence of (partial) Latin squares with large (possibly transitive) autotopism groups.