GAP

GAP (Groups, Algorithms, Programming) is a system for computational discrete algebra, with particular emphasis on group theory.

Kernel contributions

I contribute to the GAP kernel (written in C), working on the memory manager (GASMAN), the type system, and general performance improvements. I wrote about some of this in a blog post on GASMAN.

Packages

My GAP packages centre on partition backtracking — algorithms for searching in permutation groups. The story has two generations.

Partition backtrack (Leon-style)

Leon’s partition backtrack algorithm is the classical approach to problems like group intersection and stabiliser computation in permutation groups. I have two implementations:

  • BacktrackKit — a clean, simple teaching implementation of Leon’s partition backtrack. Written for clarity, not speed.
  • ferret — a polished, improved implementation with better performance. Distributed with GAP.

Graph backtracking

We overhauled partition backtrack in a series of papers, replacing it with algorithms based on directed graphs and refiners:

  • Jefferson, Pfeiffer, Waldecker, Wilson. New refiners for permutation group search. Journal of Symbolic Computation, 2019.
  • Jefferson, Pfeiffer, Waldecker, Wilson. Permutation group algorithms based on directed graphs. Journal of Algebra, 2021.
  • Jefferson, Waldecker, Wilson. Perfect refiners for permutation group backtracking algorithms. Journal of Symbolic Computation, 2023.
  • Jefferson, Waldecker, Wilson. Computing canonical images in permutation groups with Graph Backtracking. Journal of Computational Algebra, 2023.

Again, there are two implementations:

  • GraphBacktracking — a simple teaching implementation of graph backtracking. Written for clarity.
  • vole — the high-performance Rust implementation.

Canonical images

  • images — finds canonical images of combinatorial structures under the action of permutation groups. Based on: Jefferson, Jonauskyte, Pfeiffer, Waldecker. Minimal and canonical images. Journal of Algebra, 2019.

What should I use?

  • Want canonical images of combinatorial structures? Use images.
  • Want to compute in permutation groups (group intersection, coset intersection, etc.)? ferret is distributed with GAP. For better performance, download vole.
  • Want to learn how these algorithms work? Use BacktrackKit and GraphBacktracking — but be warned, these teaching implementations can be over 100x slower than ferret/vole.