New refiners for permutation group search

Christopher Jefferson; Markus Pfeiffer; Rebecca Waldecker

doi:10.1016/j.jsc.2017.12.003

New refiners for permutation group search

Christopher Jefferson, Markus Pfeiffer, Rebecca Waldecker

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

Abstract

Partition backtrack is the current generic state of the art algorithm to search for subgroups of a given permutation group. We describe an improvement of partition backtrack for set stabilizers and intersections of subgroups by using orbital graphs. With extensive experiments we demonstrate that our methods improve performance of partition backtrack – in some cases by several orders of magnitude.

Original language	English
Pages (from-to)	70-92
Number of pages	23
Journal	Journal of Symbolic Computation
Volume	92
Early online date	11 Jan 2018
DOIs	https://doi.org/10.1016/j.jsc.2017.12.003
Publication status	Published - May 2019

Keywords

Backtrack search
Refiners
Permutation groups
Algorithmic group theory
Computational algebra
Partition backtrack

Access to Document

10.1016/j.jsc.2017.12.003Licence: CC BY

Jefferson_2018_JSC_newrefiners_CC
Copyright © 2018 The Authors. Published by Elsevier Ltd. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).
Final published version, 527 KBLicence: CC BY

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
Combining Constraints and Verification: Combining Constraints and Verification
Jefferson, C. A. (PI)
EPSRC
31/07/14 → 30/07/17
Project: Standard

Cite this

@article{5286402763bf4373b4a17b794318a6ea,

title = "New refiners for permutation group search",

abstract = "Partition backtrack is the current generic state of the art algorithm to search for subgroups of a given permutation group. We describe an improvement of partition backtrack for set stabilizers and intersections of subgroups by using orbital graphs. With extensive experiments we demonstrate that our methods improve performance of partition backtrack – in some cases by several orders of magnitude.",

keywords = "Backtrack search, Refiners, Permutation groups, Algorithmic group theory, Computational algebra, Partition backtrack",

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

year = "2019",

month = may,

doi = "10.1016/j.jsc.2017.12.003",

language = "English",

volume = "92",

pages = "70--92",

journal = "Journal of Symbolic Computation",

issn = "0747-7171",

publisher = "Academic Press/Elsevier ",

}

TY - JOUR

T1 - New refiners for permutation group search

AU - Jefferson, Christopher

AU - Pfeiffer, Markus

AU - Waldecker, Rebecca

PY - 2019/5

Y1 - 2019/5

N2 - Partition backtrack is the current generic state of the art algorithm to search for subgroups of a given permutation group. We describe an improvement of partition backtrack for set stabilizers and intersections of subgroups by using orbital graphs. With extensive experiments we demonstrate that our methods improve performance of partition backtrack – in some cases by several orders of magnitude.

AB - Partition backtrack is the current generic state of the art algorithm to search for subgroups of a given permutation group. We describe an improvement of partition backtrack for set stabilizers and intersections of subgroups by using orbital graphs. With extensive experiments we demonstrate that our methods improve performance of partition backtrack – in some cases by several orders of magnitude.

KW - Backtrack search

KW - Refiners

KW - Permutation groups

KW - Algorithmic group theory

KW - Computational algebra

KW - Partition backtrack

U2 - 10.1016/j.jsc.2017.12.003

DO - 10.1016/j.jsc.2017.12.003

M3 - Article

SN - 0747-7171

VL - 92

SP - 70

EP - 92

JO - Journal of Symbolic Computation

JF - Journal of Symbolic Computation

ER -

New refiners for permutation group search

Abstract

Keywords

Access to Document

Fingerprint

Projects

H2020 OPENDREAMKIT: OPENDREAMKIT (partner)

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

Combining Constraints and Verification: Combining Constraints and Verification

Cite this