Slowdown caused by `IsHandledByNiceMorphism`

[ChrisJefferson]

The following code (from an example in sla, requires sla loading, but once we have a matrix group we don't need it any more):

gap> L:= SimpleLieAlgebra("E",8,Rationals);;
gap> no:= NilpotentOrbits(L);; 
gap> C:= ComponentGroup( no[41] ); 
<matrix group with 2 generators>
gap> Elements(C);

Here is a backtrace of where it gets stuck:

rep[Position( orb, pnt )] * gens[gen] / rep[Position( orb, img )] at /Users/caj/files/reps/gap/gap/lib/grpramat.gi:325 called from
IsFinite( G ) at /Users/caj/files/reps/gap/gap/lib/grpramat.gi:282 called from
IsFinite( grp ); at /Users/caj/files/reps/gap/gap/lib/grpramat.gi:269 called from
IsFinite( Image( NiceMonomorphism( G ), G ) ) at /Users/caj/files/reps/gap/gap/lib/grpramat.gi:258 called from
IsHandledByNiceMonomorphism( obj[i] ) at /Users/caj/files/reps/gap/gap/lib/grpnice.gd:258 called from
Enumerator( D ) at /Users/caj/files/reps/gap/gap/lib/domain.gi:269 called from
EnumeratorSorted( coll ) at /Users/caj/files/reps/gap/gap/lib/coll.gi:316 called from
AsSSortedList( coll ) at /Users/caj/files/reps/gap/gap/lib/list.gi:4000 called from

Looks like IsFinite( Image( NiceMonomorphism( G ), G ) ) gets stuck. I think the fundamental issue is that for this, Elements(C) is fast, while IsFinite(C) takes about 4 minutes on my machine.

[ThomasBreuer]

Elements( C ) eventually calls Enumerator( C ).

In GAP 4.14.0, the method that is chosen for C creates a list of group elements by starting with the trivial subgroup and then forming successive closures with the given generators. This takes about 10 seconds on my computer.

In the master branch, there is (since #5970 got merged) an Enumerator method that uses a nice monomorphism provided the group is finite, and for that, finiteness gets tested.

(The group consists of 248 by 248 matrices over the cyclotomic field CF(3). The first step in computing a nice monomorphism is to create a rational matrix group, which consists of 486 by 496 matrices, and the nice monomorphism of that group should be a permutation group. (For me, this computation did not finish yet.)

I am not sure what to do in this situation: We have a potentially infinite group. Simply enumerating the elements is better than setting up a nice monomorphism if the group is small, and we could argue that this is probably the case if somebody asks for the list of elements. For other functions than Elements, this argument is not valid.

[ThomasBreuer]

Actually there is a second problem (which is independent of the question whether a nice monomorphism should be used here): After switching to a rational matrix group in the first step, GAP decides the finiteness question for that group (the order is 120), I think by computing a reduction to a matrix group over a finite field. However, then this reduction is thrown away, and GAP tries to compute another nice monomorphism for the rational matrix group, which apparently is very expensive, much more than the finiteness check.

[fingolfin]

Yeah for matrix groups over number fields we have better code in OSCAR. But even with the code in GAP, it could do better, by not throwing away the reduction but rather using it as a nice monomorphism. I wonder if we could hack that together in this case?

[ThomasBreuer]

Yes, I will make a proposal for that.

What about the idea to omit Elements (Enumerator) from the list of "nice monomorphism supported" operations, such that the generic method gets used?

[fingolfin]

Thomas and me talked a bit more about this today. While we don't have plans to port all the improvements GAP has in this area back to GAP, perhaps some things can be adjusted after all?

So what happens is this:

1. First GAP computes a nice monomorphism from C into a new group, which works and is fast: the result is a larger rational matrix group:

gap> A:=Image(NiceMonomorphism(C));; time;
261
gap> DimensionOfMatrixGroup(A);
496
gap> FieldOfMatrixGroup(A);
Rationals

This group is not integral. So when we ask whether it is finite, GAP calls InvariantLattice(A) to find a way to conjugate A into an integral matrix group. On my computer this succeeds in about 10 seconds. I wonder if this can't be done faster...

Anyway, next step is to conjugate A into an integral group G (takes another 0.37 seconds).

Checking whether that group is an integer matrix groups via IsIntegerMatrixGroup(G) takes another 3 seconds (!) due to it computing determinants.

This then leads us to a method in lib/grpramat.gi starting in about line 300 which attempts to test finiteness "via Minkowski kernel (short but not too efficient)".

This then takes "forever" in case of our 496x496 integer matrix group.

But there is a much better algorithm for handling this implemented in OSCAR and based on Detinko, Flannery, O'Brien "Recognizing finite matrix groups over infinite fields", Section 4.2 -- the general version of that is not easy to implement in GAP as it requires working with number fields, but the basic case over the rationals (!!) should be easily transferable to GAP (in particular: we can also avoid the call to InvariantLattice).

I've whipped up a quick implementation of that in PR #6008 and it gets the example down to 5 seconds (while in GAP 4.14.0 it takes about 250 seconds)