`LowIndexSubgroups` for matrix groups is slow

[fingolfin]

This is slow:

gap> LowIndexSubgroups(SL(2,5), 50);; time;
3207

But converting the matrix group to a permutation group is much faster.

gap> LowIndexSubgroups(NiceObject(SL(2,5)), 50);; time;
39

My guess is that some or several operations invoked by LowIndexSubgroups resort to a very slow fallback (like, something doing enumeration or whatever). Of course we could try to install a "nice monomorphism method" for LowIndexSubgroups (and this is probably optimal for now, until we have composition trees for matrix groups properly). But it would also be nice what are the intermediate operations that are causing the slowness, In other words: ideally someone would run a profiler to figure that out, and then we tweak some more methods.

(In general I wonder if we should add a global flag which disables all "fully generic fallbacks" which do things like enumeration -- I would prefer to see an error in those cases, so I can identify "missing" functions. I am not proposing this to be the new default, just as a feature for pro users to help them debug performance issues).

[ThomasBreuer]

The slow part is the conjugacy test for subgroups of a matrix group, which uses the generic RepresentativeAction method. For permutation groups, RepresentativeAction essentially delegates to ConjugatorPermGroup.

The problem disappears if we let RepresentativeAction( G, H, K, op ) delegate to the images under the nice monomorphism, but perhaps we can do even better.

[hulpke]

Before making a major investment in special "nice monomorphism" methods, it mighty be worth thinking how much we want to leverage composition tree (the recog package) and rather implement methods that use the solvable radical setup?

The one bit that holds us back is the lack of verification. But if we go through the effort of nice monomorphism, we know the group order and thus can verify the tree structure easily.

[fingolfin]

I have a sabbatical this winter and one of the things I'd like to work on is recog, esp. integrating the verification routines, the new constructive recognition methods for classical groups etc., and I'd be delighted if others contributed as well of course. (Beyond that on the long term we of course also need code which e.g. refines the initial composition tree into a "nicer" one along etc.)

However this won't be quickly there. Installing a few more "nice monomorphism methods" in contrast can be done very quickly and doesn't seem like a major investment to me?

In other words, I don't see why we shouldn't do both?

[hulpke]

No opposition to do both, but the nice monomorphism model looks as if it will stumble soon again on another command after having gotten it over one hurdle.

[ThomasBreuer]

Currently my idea is not to install a nice monomorphism based method for LowIndexSubgroups but one for IsConjugate, and to replace the RepresentativeAction( ... ) <> fail call in the available LowIndexSubgroups method by an IsConjugate( ... ) call.

This way, better methods for matrix groups (which eventually will become available) do not get overridden. Furthermore, the advantage over a nice monomorphism based method for RepresentativeAction is that the nice monomorphism need not translate a conjugating element back to the matrix group side, which then just gets compared with fail.

I will provide a pull request for this idea. (Perhaps some other computations will be affected by this change.)

[ThomasBreuer]

The pull request #6116 is just a first step. We can do more:

• The IsConjugate( G, U, V ) tests via a nice monomorphism have to check whether U and V are in the source of the nice monomorphism of G. In the situation given in the LowIndexSubgroups method in question, this condition is a priori known to be satisfied. A "no check" variant would be useful (likely also in other situations).
• The test whether U is contained in G would be cheap if G would be the parent of U. Currently the groups returned by LowIndexSubgroups have in general different parents; each parent depends on where the subgroup was found as an iterated maximal subgroup of G; we could change this, but that would introduce some overhead.
• ~~An obvious improvement of the LowIndexSubgroups method for finite groups would be to initialize the local variables m and all such that the relevant maximal subgroups are already contained. Note that we know already that they are unique up to G-conjugation, this need not be tested again.~~ (has been done in the second commit of #6116)
• My interpretation of the function SubgroupsOrbitsAndNormalizers is that its approach is cheaper than IsConjugate tests. This function takes a group and a list of subgroups, and returns a list of representatives of the given subgroups under conjugation. The idea is to compute iteratively all conjugates of a member of the list, and to remove list members that are equal to some of these conjugates. (This is apparently cheaper than IsConjugate tests, at least if the classes are short.) From this point of view, I do not understand why LowIndexSubgroup uses IsConjugate tests for comparing new candidates with the subgroups that were obtained in earlier steps. A modified version of SubgroupsOrbitsAndNormalizers could take a second list of subgroups, and check whether the conjugates in question are contained in this list. This way, no IsConjugate call would be necessary at all. What am I missing?

[hulpke]

We can do more:

• My interpretation of the function SubgroupsOrbitsAndNormalizers is that its approach is cheaper than IsConjugate

Yes and no. The method for LowIndexSubgroups is a quick implementation. (The intention was to have the functionality at all with code that is written in a few minutes, rather than spending a few days on a more elaborate implementation. I did not realize anyone was actually using it for larger examples.)

It calls SubgroupsOrbitsAndNormalizers on the whole list of subgroups to avoid more complicated avoidance of duplicates arising through two different paths. Clearly this could be improved, if someone is interested in putting more effort into this operation.

SubgroupsOrbitsAndNormalizers is intended as a function that will take care of eliminating conjugate subgroups from a list while avoiding conjugacy tests through appropriate (possibly representation-dependent) invariants, such as order, orbits. Compared with iterative IsConjugate calls we save on the repreated computation of such invariants. Furthermore, this process of finding invariants will also often help by finding smaller supergroups of the respective normalizers.

I do not understand why LowIndexSubgroup uses IsConjugate tests for comparing new candidates with the subgroups that were obtained in earlier steps.

The problem is that the lattice is not guaranteed to be distributive. We might have two chains of iterated maximals: G>A>B and G>C>D>E, such that E and B are conjugate in G, but none of the other subgroups are.

[ThomasBreuer]

@hulpke Thanks for the explanation.

Conjugacy checks are a bottleneck in many applications, speeding them up (for example by using suitable invariants) is of general interest, it would be good to have more tools for that, see for example the code in lib/PositionConjugacyClass.g* in the new GAP package https://github.com/frankluebeck/UTable.