immediate descendants of 2^6 of stepsize 2 takes >24hours...

[heikodietrich]

Lieber Max,

In GAP, Version 4.7.8 of 09-Jun-2015, on Linux, the following behavior is odd.
The same computation takes 100s in Magma.

G:=AbelianGroup([2,2,2,2,2,2]);
G:=Pq(G:Prime:=2);
D:=PqDescendants(G:Prime:=2,StepSize:=2);

(is running for 24h now) ... it's stuck here:

^CError, user interrupt in
  h := Position( orbit[j], pt ); called from 
BlockPosition( orbit, y ) called from
BlockOrbitStabilizer( A, glMats, os, oper, info ) called from
PGHybridOrbitStabilizer( A, glMats, agMats, pt, OnBasis, rec(
     ) ); called from
PGMatrixOrbitStabilizer( A, V, W, R ); called from
PGOrbitStabilizerBySeries( A, baseU, chop ); called from
...  at line 15 of /tmp/tmdOfhUW/GAP_rep
you can 'return;'
brk> 

[fingolfin]

Thanks for the report.

The place the computation is stuck in is within autpgrp, which implements an orbit algorithms that require O(n^2) time (or worse) instead of O(n) (or at least O(n log(n)) due to not using a dictionary to perform lookups in the partial orbit.

I have a patch for autpgrp which improves this. I thought that I sent it to Bettina, but given that it is not contained in the latest autpgrp code, that seems to wrong?!? I need to follow up on this.

Anyway: With that patch, things are quite a bit faster (mind you, faster, not necessarily fast ;-): I just started two instances of GAP with your example, one with regular autpgrp, one with my version; the former has been stuck in an automorphism computation for at least an hour now, the latter has proceed to a point where GAP asked for more memory, twice (I did not start it with more than the default, even though this is a 64 GB machine).

However, while the second process is much faster, it still is working on the problem after over an hour now; so compared to the 100 seconds you report for Magma, that's certainly very bad.

Right now, it is still (or again) stuck in autpgrp, so I think the issue sits there.

Indeed, I recall that I once looked into the autpgrp code to debug another example where GAP was muuuch slower than magma to compute the automorphism group of a p-group, and thought that one could do perhaps better, but it's been quite some time I had that look, and I might misremember. And perhaps there is some structural "trick" that Magma exploits but autpgrp does not?
I certainly know that I spent a lot of time improving a similar algorithm for the "F-solvable group generation" algorithm Bettina and me developed...

Anyway: I am now letting that computation run some more, to see if it terminates over the weekend or not. Sure, that's still horribly bad compared to Magma, but it would still be good to know whether it at least completes eventually.

As it is, though, it seems the issue is in autpgrp.