Minimal and canonical images

Christopher Jefferson; Eliza Jonauskyte; Markus Pfeiffer; Rebecca Waldecker

doi:10.1016/j.jalgebra.2018.11.009

Minimal and canonical images

Christopher Jefferson, Eliza Jonauskyte, Markus Pfeiffer, Rebecca Waldecker

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

Abstract

We describe a family of new algorithms for finding the canonical image of a set of points under the action of a permutation group. This family of algorithms makes use of the orbit structure of the group, and a chain of subgroups of the group, to efficiently reduce the amount of search that must be performed to find a canonical image.

We present a formal proof of correctness of our algorithms and describe experiments on different permutation groups that compare our algorithms with the previous state of the art.

Original language	English
Pages (from-to)	481-506
Journal	Journal of Algebra
Volume	521
Early online date	22 Nov 2018
DOIs	https://doi.org/10.1016/j.jalgebra.2018.11.009
Publication status	Published - 1 Mar 2019

Keywords

Minimal images
Canonical images
Computation
Group theory
Permutation groups

Access to Document

10.1016/j.jalgebra.2018.11.009Licence: CC BY

Jefferson-2018-Minimal-canonical-481-CC
© 2018 The Authors. Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/ ).
Final published version, 485 KBLicence: CC BY

https://arxiv.org/abs/1703.00197v2

RS Research Fellowship Renewal: RS Research Fellowship Renewal
Jefferson, C. A. (PI)
The Royal Society
1/10/18 → 31/03/22
Project: Fellowship
H2020 OPENDREAMKIT: OPENDREAMKIT (partner)
Linton, S. A. (PI) & Konovalov, O. (CoI)
European Commission
1/09/15 → 31/08/19
Project: Standard
CoDiMa: CoDiMa (CCP in the area of Computational Discrete Mathematics)
Linton, S. A. (PI) & Konovalov, O. (CoI)
EPSRC
1/03/15 → 29/02/20
Project: Standard

Cite this

@article{d006d944ed09434aa9933c4441f817d4,

title = "Minimal and canonical images",

abstract = "We describe a family of new algorithms for finding the canonical image of a set of points under the action of a permutation group. This family of algorithms makes use of the orbit structure of the group, and a chain of subgroups of the group, to efficiently reduce the amount of search that must be performed to find a canonical image. We present a formal proof of correctness of our algorithms and describe experiments on different permutation groups that compare our algorithms with the previous state of the art.",

keywords = "Minimal images, Canonical images, Computation, Group theory, Permutation groups",

author = "Christopher Jefferson and Eliza Jonauskyte and Markus Pfeiffer and Rebecca Waldecker",

note = "All authors thank the DFG (Wa 3089/6-1) and the EPSRC CCP CoDiMa (EP/M022641/1) for supporting this work. The first author would like to thank the Royal Society, and the EPSRC (EP/M003728/1). The third author would like to acknowledge support from the OpenDreamKit Horizon 2020 European Research Infrastructures Project (#676541). The first and third author thank the Algebra group at the Martin-Luther Universit{\"a}t Halle-Wittenberg for the hospitality and the inspiring environment. The fourth author wishes to thank the Computer Science Department of the University of St Andrews for its hospitality during numerous visits.",

year = "2019",

month = mar,

day = "1",

doi = "10.1016/j.jalgebra.2018.11.009",

language = "English",

volume = "521",

pages = "481--506",

journal = "Journal of Algebra",

issn = "0021-8693",

publisher = "Academic Press/Elsevier ",

}

TY - JOUR

T1 - Minimal and canonical images

AU - Jefferson, Christopher

AU - Jonauskyte, Eliza

AU - Pfeiffer, Markus

AU - Waldecker, Rebecca

N1 - All authors thank the DFG (Wa 3089/6-1) and the EPSRC CCP CoDiMa (EP/M022641/1) for supporting this work. The first author would like to thank the Royal Society, and the EPSRC (EP/M003728/1). The third author would like to acknowledge support from the OpenDreamKit Horizon 2020 European Research Infrastructures Project (#676541). The first and third author thank the Algebra group at the Martin-Luther Universität Halle-Wittenberg for the hospitality and the inspiring environment. The fourth author wishes to thank the Computer Science Department of the University of St Andrews for its hospitality during numerous visits.

PY - 2019/3/1

Y1 - 2019/3/1

N2 - We describe a family of new algorithms for finding the canonical image of a set of points under the action of a permutation group. This family of algorithms makes use of the orbit structure of the group, and a chain of subgroups of the group, to efficiently reduce the amount of search that must be performed to find a canonical image. We present a formal proof of correctness of our algorithms and describe experiments on different permutation groups that compare our algorithms with the previous state of the art.

AB - We describe a family of new algorithms for finding the canonical image of a set of points under the action of a permutation group. This family of algorithms makes use of the orbit structure of the group, and a chain of subgroups of the group, to efficiently reduce the amount of search that must be performed to find a canonical image. We present a formal proof of correctness of our algorithms and describe experiments on different permutation groups that compare our algorithms with the previous state of the art.

KW - Minimal images

KW - Canonical images

KW - Computation

KW - Group theory

KW - Permutation groups

U2 - 10.1016/j.jalgebra.2018.11.009

DO - 10.1016/j.jalgebra.2018.11.009

M3 - Article

SN - 0021-8693

VL - 521

SP - 481

EP - 506

JO - Journal of Algebra

JF - Journal of Algebra

ER -

Minimal and canonical images

Abstract

Keywords

Access to Document

Fingerprint

Projects

RS Research Fellowship Renewal: RS Research Fellowship Renewal

H2020 OPENDREAMKIT: OPENDREAMKIT (partner)

CoDiMa: CoDiMa (CCP in the area of Computational Discrete Mathematics)

Cite this