[GAP Forum] Performance issue

[Alexander Hulpke]

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