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 <hul...@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: hul...@math.colostate.edu, Phone: ++1-970-4914288
http://www.math.colostate.edu/~hulpke
_______________________________________________
Forum mailing list
Forum@mail.gap-system.org
http://mail.gap-system.org/mailman/listinfo/forum
