[GAP Forum] Fast Orbit Computation for Custom Objects?

[Sven Reichard]

Dear Alexander,

thank you for your thorough answer. My objects aren't terribly  
complicated. They are partitions of [1..n] (for some fixed n) that  
have some classes marked as "special". They are local to a search  
algorithm, so their representation can be easily changed. Currently I  
represent them as records with two components - the partition itself  
as a set of sets, and the subset of special classes. From your remarks  
I gather that I would be better off with an ordered list (of length 2)  
of sets of sets.

For further background: Some partitions are "stable", and I can  
compute - at considerable cost -  the coarsest stable refinement for a  
given partition. The set of stable partitions is invariant under some  
subgroup G of SymmetricGroup(n). Now I would like to enumerate all  
stable partitions up to isomorphism under G. This is related to the  
enumeration of Schur rings. In the search objects the partition is the  
coarsest stable partition containing the given special classes.

Cheers,
Sven.

Zitat von Alexander Hulpke <hulpke at math.colostate.edu>:

> 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