[GAP Forum] Performance issue

[Mathieu Dutour]

Dear Gap forum,

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)

which is very long while the answer is clearly
a product of the form
Sym(X1) x Sym(X2) x ...... x Sym(Xn)

I understand very well that a general purpose
program like GAP cannot possibly find the best
algorithm in every situation. But I encounter
that problem already two times in my work and
wrote according specialized procedures.

On the other hand for this special action
"Permuted", there is perhaps another way to deal
with for general permutation groups: write v as
list of sets and compute the stabilizer by a tower
of stabilizers (as explained by Alexandre Hulpke
a few months ago)

  Mathieu

PS: see below the code of two approaches explained
above:
   "special ad-hoc code"
CycleFromList:=function(n, eList)
  local eL, i, iNext;
  eL:=[1..n];
  for i in [1..Length(eList)]
  do
    iNext:=NextIdx(Length(eList), i);
    eL[eList[i]]:=eList[iNext];
  od;
  return PermList(eL);
end;

__SymmetricPermutedStabilizer:=function(eVect)
  local p, H, ListGen, eVal, FC, FuncInsert;
  p:=Length(eVect);
  H:=Set(eVect);
  ListGen:=[];
  FuncInsert:=function(eGen)
    if eGen<>() then
      Add(ListGen, eGen);
    fi;
  end;
  for eVal in H
  do
    FC:=Filtered([1..p], x->eVect[x]=eVal);
    FuncInsert(CycleFromList(p, FC));
    if Length(FC)>=3 then
      FuncInsert(CycleFromList(p, FC{[1,2]}));
    fi;
  od;
  return PersoGroupPerm(ListGen);
end;

__SymmetricPermutedRepresentativeAction:=function(eVect1, eVect2)
  local p, H1, H2, ListStatus2, i, eList, eVal, iPos;
  H1:=Collected(eVect1);
  H2:=Collected(eVect2);
  if H1<>H2 then
    return fail;
  fi;
  p:=Length(eVect1);
  ListStatus2:=[];
  for i in [1..p]
  do
    ListStatus2[i]:=1;
  od;
  eList:=[];
  for i in [1..p]
  do
    eVal:=eVect1[i];
    iPos:=1;
    while(true)
    do
      if ListStatus2[iPos]=1 then
        if eVect2[iPos]=eVal then
          eList[i]:=iPos;
          ListStatus2[iPos]:=0;
          break;
        fi;
      fi;
      iPos:=iPos+1;
    od;
  od;
  return PermList(eList);
end;




   "tower of stabilizer"
FuncStabilizer:=function(G, v)
  local Stab, eVal;
  Stab:=Group(SmallGeneratingSet(G));
  for eVal in Set(v)
  do
    Stab:=Stabilizer(Stab, Filtered([1..Length(v)], x->v[x]=eVal), OnSets);
    Stab:=Group(SmallGeneratingSet(Stab));
  od;
  return Stab;
end;

-- 
Mathieu Dutour Sikiric		Researcher in Math
Tel. (+972)2 65 84 103		and Computer Science
Fax. (+972)2 56 30 702		Einstein Institute of Mathematics
E-mail: Mathieu.Dutour at ens.fr	Hebrew University of Jerusalem
http://www.liga.ens.fr/~dutour	Israel