Meataxe performance for reducible modules is often quite bad

[fingolfin]

In PR #6276 I made some things much faster for irreducible modules. But the example there trivially extends to reducible examples that are still far slower than they ought to be -- both when comparing to Magma or when considering trivial adhoc tests one could implement to make them faster. But of course we want generic (not adhoc) code, and a fix that hopefully doesn't make the existing fast path noticeably slower.

E.g.:

n:=10;;   # increase this to make the effect even stronger
G:=GL(56,GF(25));;
H:=Subgroup(G, Concatenation(GeneratorsOfGroup(G),List([1..n],i->PseudoRandom(G))));;
dn:=g ->DirectSumGModule(NaturalGModule(g),NaturalGModule(g));;

then

# fast
gap> MTX.IsIrreducible(dn(H)); time;
false
46
gap> MTX.Indecomposition(dn(G));; time;
84

# slow
gap> MTX.Indecomposition(dn(H));; time;
9130
gap> MTX.Indecomposition(dn(H));; time;
4785
gap> MTX.Indecomposition(dn(H));; time;
9190

No way it should take several seconds to compute that decomposition. The bottleneck is in SMTX.BasisModuleHomomorphisms and there in SpinHom.

I notice that we end up calling SMTX_AddEqns 1234 times; which amounts to 2*56=112 times as many "equation" it tries to produce, i.e., 138208 ; of those 137988 turn out to be redundant, so just 220 end up being relevant.

Now the problem increases with the number of generators; and here of course we have 10 redundant generators. Perhaps we can do a better job of discovering this?

[fingolfin]

Some progress is made in PR #6289 and #6290 but more is needed.

There are also other really bad examples, e.g. this one:

MeataxeExample2 := function(n, F)
  local mat;
  mat := IdentityMat( n, F );;
  mat{[1,2]}{[1,2]} := [[0,1],[1,0]]*One(F);;
  ConvertToMatrixRep(mat);;
  return GModuleByMats([mat],F);;
end;

M:= MeataxeExample2(300, GF(2));
MTX.BasesCompositionSeries(M);; time;  # takes ~650 ms
indec:=MTX.Indecomposition(M);; time;  # takes "forever"

So we are computing a 300x300 module which has a 2x2 block and otherwise is trivial. A human can look at this, manually write down the result, and enter that into GAP, and handily beat GAP doing that...

Part of the problem is that it tries to compute the endomorphism algebra, which contain the full matrix ring of rank 298, so its dimension is close to $300^2=90000$.