Dear GAP-Forum,
On Sep 22, 2005, at 5:14 AM, Mathieu Dutour wrote:
I have a performance problem with the following:
v:=[1,2,4,5,1,2,4,2,6,2,5,1,3,5];
GR:=SymmetricGroup(Length(v));
Stabilizer(GR, v, Permuted); (very very slow)
There are three different methods for `Stabilizer' built into GAP.
The first is a generic Orbit/Stabilizer algorithm, that will compute
the orbit of the point under the specified action and then construct
the stabilizer from Schreier generators.
The second is a variant for solvable groups that utilizes that the
orbits of a normal subgroup form blocks. Memory requirements are
similar as with variant 1 but it will run faster.
Finally there are special cases for a few specific actions:
A group on its elements or subgroups (Centralizer, Normalizer)
A permutation group on points, tuples, sets (via backtrack routines).
The aim here is not to cover any possible action with special
routines, but to have routines for ``hard'' problems from which other
stabilizers can be built easily if possible.
Similar remarks hold for `RepresentativeAction'.
`Permuted' is not one of these specific actions, thus the first
variant is used which explains the long runtime.
An easy way to deal with `Permuted' is to realize that we want to
stabilize the index sets of elements at the same position. Thus:
idx:=List(Set(v),i->Filtered([1..Length(v)],j->v[j]=i)); # get index
sets
Sort(idx,function(a,b) return Length(a)<Length(b);end); # have
stabilizers of small sets first
gap> stb:=Iterated(Concatenation([GR],idx),
> function(G,S) return Stabilizer(G,S,OnSets);end); #
iterated set stabilizer
will return the result quickly.
Best wishes,
Alexander Hulpke
_______________________________________________
Forum mailing list
[email protected]
http://mail.gap-system.org/mailman/listinfo/forum
