[GAP Forum] Fast Orbit Computation for Custom Objects?

Sat May 18 18:48:04 BST 2013

Dear Sven,

I would second Attila's suggestion to use the Orb package. Orb
contains generic orbit algorithms, and implementations for hash
tables.

If I were try to find an orbit of a partition with special classes
under a group I would probably represent the partition as a flat list
of integers: [[1,2],[3,4,6],[5]] where [1,2] and [5] are special
becomes [1,1,2,2,3,2,1,0,1] (the value in the i-th position, i=1..6,
is class that i belongs to and position j+6 is 1 if the j-th class is
special and 0 if it is not (j=1..3)). Then you can compute the orbit
by doing:

o:=Orb(G, [1,1,2,2,3,2,1,0,1], MyAction, rec(forflatplainlists:=true));
Enumerate(o);

where G is your group,  [1,1,2,2,3,2,1,0,1] is your partition,
MyAction is the action of G on partitions with special classes, and
the final argument is a record which can be used to pass options to
Orb. In this case, forflatplainlists:=true tells Orb that the points
in the orbit you are trying to calculate are flat plain lists (lists
containing no subobjects) and Orb knows how to hash such objects
efficiently. Doing this you can take advantage of all the
functionality of the Orb package, including hash functions and so on,
without having to write your own code beyond the function MyAction. In
particular, you can probably get this to work, with good performance,
in a relatively short amount of time.

I'd be happy to help if you have any further queries, or if something
I've written is unclear.

Regards,

James

On 18 May 2013 08:29, Sven Reichard <Sven.Reichard at mailbox.tu-dresden.de> wrote:
> 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
>
>
>
>
> _______________________________________________
> Forum mailing list
> Forum at mail.gap-system.org
> http://mail.gap-system.org/mailman/listinfo/forum

-- 
James Mitchell
tinyurl.com/jdmitchell

The University of St Andrews is a charity registered in Scotland : No SC013532