[GAP Forum] Speedup of GAP program - centric subgroups

[Jack Schmidt]

Just to address the theoretical question of computing centric subgroups: 
  If P is a proper centric subgroup of S, then it is contained in some 
maximal subgroup M of S and so C_S(M) <= C_S(P) <= P <= M.

A simple algorithmic change then is to use Centralizer( S, 
FrattiniSubgroup( S ) ) instead of Center( S ).  This improved 
performance a fair amount in both GAP and magma.  For GAP, 2^6 went from 
30 seconds to 7 seconds, and 2^7 went from 500 seconds to 80 seconds.

Of course, you could also check which maximal subgroups of S are 
centric, and only consider their subgroups, but it looked like over 80% 
of maximal subgroups were centric, and nearly 80% of groups had all 
maximals centric, so it may not be worth the headache.

Kasper Andersen wrote:
> Hi,
> 
> In connection with a joint project with Bob Oliver and Joana Ventura I 
> have been carrying out a number of computations for the 2-groups of 
> order at most 2^8 in Magma. To check them and to learn GAP at the same 
> time, I have tried to port my programs to GAP.
> 
> Unfortunately GAP seems to be significantly slower (a factor of acround 
> 2.7) than Magma. Before I go any further I wonder if there is a way to 
> speed up GAP. As a test I have been running the following GAP program:
> 
> iscritical := function(S,P)
>   return 1;
> end;
> 
> criticalsubgroups := function(S)
>   local kappa,SmodZ,L;
>   if IsAbelian(S) then
>     return [];
>   else
>     # Only check subgroups containg Z(S)
>     kappa:=NaturalHomomorphismByNormalSubgroup(S,Center(S));
>     SmodZ:=FactorGroup(S,Center(S));
>     L:=SubgroupsSolvableGroup(SmodZ);
>     L:=List(L,x->PreImage(kappa,x));
>     return Filtered(L,P->(iscritical(S,P) <> -1));
>   fi;
> end;
> 
> n:=2^7;
> 
> for i in [1..NumberSmallGroups(n)] do
>   S:=SmallGroup(n,i);
>   L:=criticalsubgroups(S);
>   Print(n," ",i,"\n");
> od;
> 
> Some comments are in order: To simplify the timings I have left out the 
> code for the function iscritical, so the above program simply computes 
> the conjugacy classes of subgroups P containing Z(S) for all 2-groups S 
> of order 2^7. Moreover my original function does not return true/false 
> but rather -1 (=false), 0 (=undecided) and 1 (=true). For simplicity I 
> have left this in.
> 
> Unfortunaly even this simple program runs a factor of 2.7 slower than 
> the corresponding Magma program. Are there any ways to speed this up?
> 
> Another question: One of the conditions for criticality is that P is 
> centric in S, i.e. that C_S(P) is contained in P. Does anyone know any 
> better algorithm for computing all such subgroups than testing all 
> subgroups containing Z(S) one by one?
> 
> best wishes,
> 
> Kasper Andersen
> 
> _______________________________________________
> Forum mailing list
> Forum at mail.gap-system.org
> http://mail.gap-system.org/mailman/listinfo/forum