[GAP Forum] introduction to backtrack algorithm with ordered partitions

[Bill Allombert]

On Fri, Sep 25, 2020 at 03:15:06PM +0000, Christopher Jefferson wrote:
> Just to extend on Leonard's comments,
> 
> The paper New refiners for permutation group search [Christopher
> Jefferson, Markus Pfeiffer, Rebecca Waldecker] gives a brief overview
> of partitions, while extending it. "Permutation group algorithms based
> on directed graphs" gives a new, more general framework, which uses
> directed graphs.
> 
> If you are happy looking at code,
> https://www.github.com/gap-packages/ferret gives a (reasonably) clean
> reimplementation in C++, while https://github.com/peal/backtrackkit
> gives a simple, very low-performance implementation (it aims to
> produce the "right partitions", but does so in a very simple but
> inefficient way).
> 
> I also recently gave a brief overview on the topic at the Newtown
> Institute: https://www.newton.ac.uk/seminar/20200131113012201 , which
> you may (or may not) find helpful. I'm also happy to answer any
> questions, particularly about Leon's paper which myself and my
> co-authors are fairly sure we understand.

I like to thanks all of you for all the references, I have started to read
them.

In fact, I am interested in the computation of automorphisms groups of
Euclidean lattices. There is a published algorithm by Plesken and
Souvignier (1997) which uses backtracking and the randomized Schreier-Sims
algorithm. Prof Souvignier published a C implementation of this
algorithm which is widely used.

MAGMA uses a faster but unpublished algorithm whose source code is not
public. The documentation says:

The computation of the automorphism group of a lattice (i.e. the largest
matrix group that acts on the lattice) and the testing of lattices for
isometry is performed within Magma using orthogonal decomposition (due
to Gabi Nebe) and a backtrack search designed by Bill Unger in 2009. The
backtrack search is based on the Plesken-Souvignier backtrack algorithm
[PS97] together with ordered partition methods due to Leon. 

So I am left trying to understand what is the ordered partition method
and how it can be used.

Cheers,
Bill