0
$\begingroup$

So I decided to compute the first few terms of the automorphism series (finite part of the automorphism tower) for SmallGroup(16,3) in GAP in part to verify that $Aut^6(G)\simeq Aut^7(G)$ where

$Aut^k(G)=\underset{k}{\underbrace{ Aut(Aut(Aut(...}}G...)))$

Now, $Aut^6(G)$ is a group of order 442,368 (as is its automorphism group). I constructed the tower iteratively. For the first few, they are small enough to have Ids in the library, so after constructing the group with the command AutomorphismGroup, I would Id it, and then redefine the group in terms of it's library entry. Once they got too big however, instead I would use NiceMonomorphism, and then redefine the group as the NiceObject thereof. I would then further construct a minimal generating set, and redefine the group a second time as GroupWithGenerators(MinimalGeneratingSet(G)). Then I would ask for it's automorphism group, and repeat that process again, once I had $Aut^7(G)$ expressed with minimal generating set, I asked it to construct the isomorphism via IsomorphismGroups(K,Aut(K)) where K here was $Aut^6(G)$. This took literally all day to do (just finished), but for some reason the time command reported it took 1283038 which is supposed to be in milliseconds (that's roughly 21mins time then).

Two questions: #1 Why is the time so far off? #2 What I can I do with the way the groups are presented in GAP to reduce runtime and improve performance (note that the 'Nice' commands are to get it into a permutation group). I did this in the past and it didn't take nearly as long, and I know at least one other person was able to very that isomorphism in a matter of minutes at most. (My CPU is a core i5-3450, and I have 4GB ram, so lack of computer power is not the issue.)

$\endgroup$
5
  • 2
    $\begingroup$ I recommend you to ask in the GAP Forum. $\endgroup$ – Andreas Caranti Mar 12 '16 at 17:44
  • $\begingroup$ Which operating system do you have? $\endgroup$ – Alexander Konovalov Mar 12 '16 at 23:00
  • $\begingroup$ Win7-64 bit, install of GAP is 32 bit though. $\endgroup$ – Justin Benfield Mar 13 '16 at 16:01
  • $\begingroup$ Two ideas that need to be checked: timer wrapped up in 32-bit version (someone reported that this may happen in long calculations, I am not sure if that had been fixed or not) or part of the calculation used some package with external binaries (so time did not include time spent in those). $\endgroup$ – Alexander Konovalov Mar 13 '16 at 16:53
  • $\begingroup$ BTW GAP now provides experimental 64-bit version, see gap-system.org/Releases/index.html $\endgroup$ – Alexander Konovalov Mar 13 '16 at 20:20
3
$\begingroup$

For #1: Unless something weird happens under Windows, my guess would be that this was the timer overrunning and starting again from 0.

For #2: While the problems of automorphism group and group isomorphism are theoretically close, the implementation of automorphism groups is substantially better than that of group isomorphism. Isomorphism thus will take longer in current releases. As for improving the performance:

  • Convert from automorphism group to permutation group (which you do already) with NiceMonomorphism.
  • If the groups are solvable (as yours are), use IsomorphismPcGroup to represent the groups as PcGroups.
  • Otherwise apply SmallerDegreePermutationRepresentation in the hope to reduce the degree. (This indeed has changed -- NiceMonomorphism used to be more aggressive in trying to reduce the permutation degree but this was wasteful in other cases, so now we are less aggressive and have the user call the degree reduction themselves.

Indeed, on my laptop, is I replace IsomorphismGroups(K,Aut(K)) with

 K1:=Image(IsomorphismPcGroup(K));
 A:=AutomorphismGroup(K1);;
 A:=Image(NiceMonomorphism(A));
 A:=Image(IsomorphismPcGroup(A));

then IsomorphismGroups(K1,A); finishes after a few minutes on my laptop.

$\endgroup$
8
  • $\begingroup$ I'll give this a shot (and see how those commands effect runtimes for some related things I've been doing (that have involved some HUGE groups). This is the sort of thing I was looking for, thanks! $\endgroup$ – Justin Benfield Mar 13 '16 at 20:47
  • $\begingroup$ Indeed I managed to get the isomorphism in a time of 122866 (2mins 2.866 seconds). Thanks for the answer! $\endgroup$ – Justin Benfield Mar 13 '16 at 21:41
  • $\begingroup$ As an interesting sidenote, I also tried IsomorphismSpecialPcGroup instead. Curiously, the running time was far worse: 944508 (15mins 44.508 seconds). $\endgroup$ – Justin Benfield Mar 13 '16 at 22:43
  • $\begingroup$ I think the time difference of IsomorphismSpecialPcGroup is a random fluke -- the calculation stops once an isomorphism was found and it just might have been that the first calculation happened to make this happen earlier. $\endgroup$ – ahulpke Mar 14 '16 at 0:01
  • $\begingroup$ Is the method randomized? If not, I'm not so sure, but if so, then yea, I wouldn't be surprised if there was significant variance in runtime. $\endgroup$ – Justin Benfield Mar 14 '16 at 0:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.