> < ^ From:

^ Subject:

Dear GAP-Forum,

Sebastian Egner wrote:

# the PermGroupOps.Normalizer function of gap3r4p1 may be

# improved to handle cyclic groups of low degree more efficiently.

# Maybe this has already been done in a later releases?

[code omitted]

First, I'd like to thank you for providing your code. Indeed the

original normalizer performs abysmal in such situations (for ex-

ample take the normalizer of Z_23 in M_23), your routine shows

that this can be enormously improved. As it might be of interest,

some comments about the normalizer routine:

>From version 3.4 to 3.4.1 the normalizer has not undergone major

improvements. Our current development version contains a greatly

improved normalizer routine, written by Heiko Theissen. (The rou-

tines use partition backtrack methods, introduced by Jeffrey

Leon.) The new routines are to be released with GAP 4, mainly be-

cause they utilize small but subtle changes in the stabilizer

chain concept to be introduced then. These new routines usually

yield (based on my experiences with them) a speedup of 2 or more

when applying the routines for normalizers in the symmetric group

(or large wreath products). The improvement for cyclic groups is

even higher: For example the normalizer N_G(U) for

# as smaller degrees are too fast for timing

G:=SymmetricGroup(100);

U:=Subgroup(G,[Product(G.generators)]);

takes (on a 50Mhz 486PC) 3200ms in our experimental version.

(I did not want to wait for the 3.4 version, it certainly will

be MUCH slower ...) Your version, however, takes only 800ms on

the same machine.

Your observation remains valid even in a more general context: If

U<=G, then N_G(U)/C_G(U) is isomorphic to a subgroup of Aut(U).

Centralizer computations are easier than normalizer computations.

Thus if we know enough about the automorphism group to

guess subgroups (close supergroups) for N_G(U)/C_G(U), then

we can take these subgroups and check which subgroups are actu-

ally induced by G-conjugation. For this purpose we'll have to

find representatives of conjugating elements. This is however

again in cost similar to centralizers. So, if the automorphism

group is smaller in size than G, it might be worth to use this

approach.

For cyclic groups your algorithm implements this, guessing the

whole automorphism group and searching for suitable elements. If

|U| becomes larger this might also become expensive. An easy im-

provement is to run through all subgroups of Aut(U) (which are

easily parametrized) and to check for subgroup generators if they

are induced by conjugacy in $G$. (This is described in more de-

tail in: G.Butler, An inductive scheme for computing conjugacy

classes in permutation groups, Math. Comp. 62 (1994), 363--383.)

Thus the loop

for k in PrimeResidues(r) do

in your algorithm would be changed into a loop over subgroups of

Z_r^imes and another loop over their generators. This should give

another speedup, especially if |U| is larger. As a side effect

you get fewer generators.

One can extend this approach to abelian groups U: Here we can

take the subgroup of Aut(U), which fixes the cycle structures of

all elements in U as guessed group. Certainly it has to contain

the normalizer induced subgroup; usually it is much smaller. When

using the permutation action of Aut(U) on U, this subgroup can be

computed as a set stabilizer. Another backtrack routine then

searches for the actual normalizer induced subgroup. It turns out

that the guessed group usually is in very good approximation to

the group we want, so we don't have to worry about this last

backtrack. I reckon it might be even worth to extend it to other

relatively small groups, however then the automorphism group is

not that easy to get.

I have implemented this approach for elementary abelian groups

(it would be not too hard to extend it to the general abelian

case, but I just needed elementary abelian). In computations for

my thesis, I usually have to compute normalizers of (Z_p)^d in

Z_p \wr S_n (n>=d). Even the faster normalizer choked on these

problems for higher (p,n),while the 'automorphism guessing' works

quite well. If there is interest for it, I can put a version for

GAP 3.4 on our ftp server.

Alexander

> < [top]