Applying a homomorphism to a matrix group takes much longer than applying it to its generators

[maxhauck]

Observed behaviour

Applying a homomorphism constructed using BaseChangeHomomorphism from the Forms package to a matrix group of moderate dimension takes way longer than just applying it to the generators of the group (and then reassembling the images to a group). For instance, if you do this with SO(7, 9), the homomorphism is applied to the generators in an instant, but applying it to the whole group takes at least 5 minutes (at which point I decided to abort). ssiccha: I suppose computing a stabilizer chain is what takes forever here

Expected behaviour

This shouldn't take much longer for the group than it does for just the generators.

Suggestions

@ssiccha suggests than whenever a homomorphism maps a group into a matrix group over a finite field, the RECOG package should be used in order to improve performance.

Copy and paste GAP banner (to tell us about your setup)

 ┌───────┐   GAP 4.12dev-1025-g6f2a849 built on 2021-08-26 16:21:46+0200
 │  GAP  │   https://www.gap-system.org
 └───────┘   Architecture: x86_64-pc-linux-gnu-default64-kv8
 Configuration:  gmp 6.2.0, GASMAN
 Loading the library and packages ...
 Packages:   AClib 1.3.2, Alnuth 3.1.2, AtlasRep 2.1.0, AutoDoc 2020.08.11, AutPGrp 1.10.2, Browse 1.8.12, CaratInterface 2.3.3,
             CRISP 1.4.5, Cryst 4.1.24, CrystCat 1.1.9, CTblLib 1.3.2, FactInt 1.6.3, FGA 1.4.0, Forms 1.2.6, GAPDoc 1.6.4,
             genss 1.6.6, IO 4.7.1, IRREDSOL 1.4.3, LAGUNA 3.9.3, orb 4.8.3, Polenta 1.3.9, Polycyclic 2.16, PrimGrp 3.4.1,
             RadiRoot 2.8, recog 1.3.2dev, ResClasses 4.7.2, SmallGrp 1.4.2, Sophus 1.24, SpinSym 1.5.2, TomLib 1.2.9,
             TransGrp 3.3, utils 0.69

edits by ssiccha: add a "matrix" , a comment, and formatting

[fingolfin]

Could you please provide the concrete inputs you are comparing? It is otherwise difficult to judge what's going on.

In particular, I don't understand why using recog here would be either necessary or advantageous? Could you elaborate? In any case, it's not really an option unless we'd be ready to make recog a required package, which I don't think we are.

Instead it sounds to me as if this might be a matter of installing a "missing" method or two; but without concrete inputs, its hard to say.

[fingolfin]

Also, BaseChangeHomomorphism is part of the forms package, so perhaps it'd be better to report this there, as there is probably nothing we can do about it in GAP itself?

[fingolfin]

Just had a look at this. BaseChangeHomomorphism is in forms but essentially it is just a wrapper around GAP's InnerAutomorphismNC:

InstallMethod( BaseChangeHomomorphism, [ IsMatrix and IsFFECollColl, IsField ],
  function( b, gf )
  ## This function returns an intertwiner of the general linear group
  ## induced by changing the basis of its underlying vector space

    local gl, invb, hom;
    if IsZero(Determinant(b)) then
       Error("Matrix is not invertible");
    fi;
    invb := Inverse( b );
    gl := GeneralLinearGroup(Size(b), gf);
    hom := InnerAutomorphismNC( gl, invb);
    return hom;
  end );

So we can reproduce the slowness without forms, too:

G:=SO(7,9);
aut:=InnerAutomorphism(GL(7,9), One(G));
H:=aut(G); # <-- slow

The last line is equivalent to Image(aut, G);, and the slowness comes because it tries to validate the input using IsSubset, which then ends up computing a NiceMonomorphism...

Directly calling ImagesSet(aut, G) avoids this, as ImagesSet apparently doesn't perform the same check.

I guess this could be fixed in this special case by adding a shortcut that handles the case where the "big" group is GL or SL directly. Not sure if that would be worth it, though?

In the concrete case that lead to this being reported, I'll just drop the use of BaseChangeHomomorphism