[GAP Forum] Fast Orbit Computation for Custom Objects?

[Alexander Hulpke]

Dear Forum, Dear Sven,

> I have the following data:
> - - A permutation group G;
> - - a set of objects obj;
> - - an action function.
> 
> I would like to get the following:
> - - The union D of the orbits of obj under G (not necessarily sorted);
> - - the action H of G on D;
> - - orbit representatives.
> 
> What I do is the following:
> 
> orbits := Orbits(G, obj, action);
> representatives := List(orbits, Representative);
> D := Union(orbits); # sorted to accelerate the next step
> H := Action(G, D, action);
> 
> This works well when action is a standard action such as OnSetsSets.
> However, for custom actions this can be very slow, suggesting that
> different algorithms are used. (In some of my examples, D has a
> million elements.)

For `Orbits' and `Action' there aren't really different algorithms used, but performance is crucially impacted by the methods available for recording the orbit elements. This is likely where you are seeing the slowdown.
Also, by first computing orbits, joining and then computing the action, you are doing the same work twice. In certain situations `SparseActionHomomorphism' might help you do this, but frankly I found that if is near impossible to define a universal optimal orbit/action routine and (given the simplicity of the code) you might be better off to code a bespoke version, modeled on the code for `SparseActionHomomorphism'.

The basic operations (and time sinks) for group actions are essentially the book keeping for the orbit elements found so far (and seed elements still to treat). To unify different approaches, GAP uses its dictionary data type. Very roughly the following things happen: (This is in the code for `NewDictionary' in lib/dict.gi.

- If no domain (set containing all orbits) is given GAP calls `DomainForAction' to try to construct one. A typical case would be a matrix group acting on vectors where the generic domain is the row space.

- If a domain exists (was given or determined in the previous step) and this domain is a `IsQuickPositionList' (finding an element is faster than binary search) or a list known to be sorted and elements can be compared cheaply by < (indicated by `CanEasilySortElements'), and the domain has not more than 2^22 elements (avoiding too long bit lists if the domain is too large) the dictionary uses `Position'. Possibly the `Enumerator' of the domain is chosen for `Position'.

- GAP calls `SparseIntKey(domain,seed)'. If this returns a function, it is taken as hash function, and a hash dictionary is used.

- Otherwise if the seed fulfills `CanEasilySortElements', the dictionary uses a sorted list of elements (binary search).

- Otherwise just a list is used with linear search by `=' only.

This means, if you act on your ``own' objects, your preference of interventions to make the code faster is the following (always if possible):

1. If you can enumerate all elements cheaply, create a domain object that provides this enumeration via \[\] and `\Position'

2. Implement a method for `SparseIntKey' that returns a hash key function.

3. If you can implement a \< comparison method for your objects. install a method for `CanEasilySortElements' that returns `true' for these.

I realize that if your objects are complicated (say you are acting on chains of subgroups) all of this is hard, but a cheap test for whether an orbit element was found already is at the heart of any orbits/action computation.

> Is there a way in GAP4 to accelerate this process, for example by
> providing hash functions? In GAP3 there existed a solution in the
> contributed file coco.grp by Theißen based on work by Faradzev et al.
> The question is whether there is a better way than porting that file
> to GAP4.

Basically all of the functionality in this file is superseded by this dictionary setup.

If you want help, please let me know what kinds of objects you are working with, in particular how they are represented.

   Alexander 

-- Colorado State University, Department of Mathematics,
Weber Building, 1874 Campus Delivery, Fort Collins, CO 80523-1874, USA
email: hulpke at math.colostate.edu, Phone: ++1-970-4914288
http://www.math.colostate.edu/~hulpke