Vole is a GAP [GAP21] package. The purpose of this manual is to describe the capabilities of Vole, and to give directions, hints, and explanations about its use.
In this manual, a permutation is defined on the set of all positive integers, but moves only finitely many points; unless otherwise stated, a group is a finite permutation group (which, by the definition of a permutation, necessarily has a finite set of moved points); and a coset is a left or right coset of such a group determined by some permutation (the parent group is unspecified).
In full generality, Vole can be used to find permutations (groups given by strong generating sets, cosets thereof, or individual representative elements) that satisfy conjunctions of particular kinds of properties, or constraints; details of these properties are given later. Problems that can be formulated in this way include, for example, the computation of normalisers, set stabilisers, subgroup intersections, and graph automorphisms, and testing subgroup conjugacy and graph isomorphism.
Vole can also compute canonical labellings and images (also known as ‘canonical forms’) of various kinds of objects under an action of an arbitrary permutation group. This includes, for example, the canonical image of a digraph under the natural action of an arbitrary permutation group, or the canonical image of a permutation group under conjugation by another. As far as we are aware, most of this canonical image functionality is not possible with existing tools.
In order to offer all of this functionality, Vole implements the graph backtracking framework, which was introduced in [JPWW21], and which generalises the partition backtracking framework of Jeffrey Leon [Leo91], [Leo97]. The functionality for canonical labellings and canonical images is underpinned, in addition, by work that is in preparation for publication, and which builds on [JJPW19].
While the GAP interface of this package is written in GAP, the main algorithms are written in Rust, for reasons of fun and performance.
Vole aims to provide a high-performance implementation of the graph backtracking framework of [JPWW21], [JPWW19].
Graph backtracking is a form of depth-first backtrack search that can be performed in a finite symmetric group, and which uses labelled digraphs to represent various aspects of the problem at hand in order to guide the search and prune the search space. The specification of the problem is given by a collection of constraints, and a collection of refiners are used to prune the search according to those constraints.
The rest of this introduction discusses the place of Vole in the GAP ‘ecosystem’, and gives information about its ongoing development. Installation instructions for Vole are given in Chapter 2, and Chapter 3 gives a tutorial for the package. Chapter 4 describes an interface to Vole that emulates the existing related functionality of GAP and its packages. Chapter 5 documents the main interface to Vole. Chapter 6 describes the constraints that can be used with Vole, while Chapter 7 explains refiners, and gives details of those that are available. Chapter 8 gives lower-level details, and instructions for the expert use of Vole.
If you encounter problems, or have any other feedback for the authors, then please create an issue on our issue tracker, or contact us by any other appropriate means. See the title page of this manual for our contact details. We published Vole so that our ideas and algorithms could be used by, and be useful to, others in the community. But without feedback, it can be difficult to know whether we are achieving this aim. Therefore we are keen to hear your comments, remarks, and complaints.
The functionality of Vole overlaps with that of GAP itself, and some of its packages. However, Vole's functionality goes further than all of them, and has the potential to offer better performance in many cases where there is an overlap. The perfomance of Vole is discussed in Section 1.4.
GAP itself
GAP [GAP21] contains an implementation of Jeffrey Leon's partition backtrack framework [Leo91], [Leo97] at the GAP level, as improved upon by Heiko Theißen [The97]. Therefore GAP already offers some of the functionality that Vole provides; the overlap is explored further in Section 4.4.
ferret
Christopher Jefferson's ferret package [Jef21] for GAP provides a C++ reimplementation of partition backtracking, which contains the orbital graph developments of [JPW19]. Vole should be seen as the spiritual successor to ferret.
images
The images package [JJPW21] provides a GAP-level implementation of the custom breadth-first search that was introduced in [JJPW19] to compute the canonical image of any set of points under the action of an arbitrary permutation group. This algorithm built upon the original algorithm of Steve Linton [Lin04] for computing minimal images of sets of points, which is available in the GRAPE package [Soi21] in lib/smallestimage.g, as SmallestImageSet. The overlap of Vole's functionality with images is detailed in Section 4.5.
Digraphs and GRAPE
The Digraphs package [BJM+21] offers interfaces to nauty [MP14] (via the NautyTracesInterface) and bliss [JK07] for computing automorphism groups and canonical images of graphs and digraphs, and their labelled variants. The overlap of Vole's functionality with Digraphs is detailed in Section 4.6. GRAPE [Soi21] also provides an interface to nauty for computing automorphism groups of graphs, and computing canonical images of graphs in the symmetric group.
BacktrackKit and GraphBacktracking
BacktrackKit [JW21a] and GraphBacktracking [JW21b] contain GAP-level reference implementations of partition backtracking and graph backtracking, respectively. They are intended to demonstrate readable code implementing these frameworks, but they are not intended to have high performance, and they are deliberately not optimized.
Vole is a work in progress – the code and its underlying mathematical theory are being developed concurrently. Therefore, some aspects of Vole are liable to change in future versions, although we will aim to maintain the primary interfaces as described in Chapters 4, 5, and 6. However, some of the lower-level details described in Sections 7 and 8 are more likely change.
The main focus of our future work on Vole will be on improving the performance of Vole, through both technical and mathematical means. This may involve changes to the design of the algorithm itself, and the improvement or addition of refiners, especially for subgroup normalisers and conjugacy. See Section 1.4 for further comments on the performance of Vole.
Our aims are for Vole to have good performance in general, and to have relatively high performance for some classes of problems that existing tools tend to find very difficult. As mentioned in Section 1.3, we are still working towards these aims.
If you encounter disappointing and/or surprising performance for your use-case, please let us know, by creating an issue on our issue tracker, or contacting us by any other appropriate means. See the title page of this manual for our contact details. This will help us to improve Vole.
The experiments in [JPWW21] showed that for some classes of problems, graph backtracking typically performs a far smaller search than does partition backtracking. Although this experimental data is very encouraging, it is clearly inherently more expensive to compute with graphs than it is to compute with ordered partitions. This means that the time gained by having a smaller number of nodes in a search does not necessarily immediately outweigh the time required to perform a larger amount of computation at each node. Therefore, in rough terms, the focus of future work is on reducing the number of search nodes further (with more sophisticated refiners), and reducing the amount of work required at each node of search (with technical optimisations).
Where there is overlap between Vole and existing functionality in the GAP ecosystem, as described in Section 1.2, we aim for Vole to perform reasonably competitively.
However, roughly speaking, there are certain problems that can be represented by ordered partitions just as well as they can by graphs. In these cases, it follows that there is nothing to be gained by using graph backtracking, while the additional overhead required by graph backtracking may make it slower overall. Vole does not yet attempt to mitigate this issue. For example, we do not yet expect Vole to match the performance of nauty (available through the Digraphs and GRAPE packages) at computing automorphisms of graphs, and canonical images of graphs in a symmetric group.
In addition, we do not expect Vole to beat images at computing canonical images of sets in groups.
There are further reasons why existing implementations may beat the current version of Vole, in some situations.
Very few special cases: Vole passes almost every problem that it receives on to the full graph backtracking algorithm, with its corresponding overheads and poor worst-case complexity. On the other hand, other implementations (particularly those in the GAP library) may provide multiple competing methods for solving a problem. Some of these methods might only apply in special cases (such as for simple groups, or abelian group, or primitive groups), and some of them might not even involve search at all. From these different methods, the system can use heuristics to choose the most appropriate one to run in each instance.
First-time compilation of Vole: When the first Vole search is executed in any particular GAP session, Vole tests whether its Rust component is compiled, and it builds the component if necessary. The check itself can take a noticeable amount of time, but compilation takes much longer. To minimise the effect, we recommend that you manually recompile Vole when you update your Vole installation via the make command, as described in Section 2.2.
Communication between the GAP layer and the Rust component: There is also a delay that is incurred when the GAP-level interface of Vole communicates with the Rust component of Vole. This is exacerbated by the fact that Vole does not yet include its own Rust-level implementation of stabiliser chains, and so it uses GAP's stabiliser chains instead. This means that GAP and the Rust component must communicate heavily during a typical search, and this can incur a significant time penalty. Implementing Rust-level stabiliser chains is a work in progress.
Fortune: The nature of backtrack search means that one algorithm may beat another just by being ‘lucky’, and (by chance) stumbling upon particularly fruitful branches early in search. Conversely, an algorithm may be ‘unlucky’ and fall down a particular unfruitful branch that a different algorithm accidentally avoids.
These factors together highlight the principle that, for users for whom performance is very important, it makes sense to experiment with the range of available tools when running computations.
Please also make sure that you are running the newest version of Vole, since newer versions should have better performance.
generated by GAPDoc2HTML