Orbits/affine spaces in GAP

[alexdegt-ops]

I need to compute the orbits of a lot (probably, hundreds of thousands) groups acting on F_2-vectors spaces of dimension 23 or 22. The groups range from (almost) the full automorphism group of the Leech lattice down to something of size 4 or 2. (Obviously, this is done in a batch, so I cannot tune this manually.) In fact, instead of the whole space I need an affine subspace of the form v * k = Z(2) for a certain invariant covector k known in advance. What is statistically the most efficient way of doing that? Currently, I'm creating a vector space

V := VectorSpace(...);

(the basis is not standard; can be pretty much anything) and then struggling between

V := Filtered(V, ...); V := OrbitsDomain(G, V);

in the hope that smaller list is better, or, in the hope that "structured" methods would be more efficient than those for plain lists (and there seems to be no affine space structure),

V := OrbitsDomain(G, V); V := Filtered(V, ...);

Both are quite slow (typically, about .5 to 1 min each action) and, for some reason, after quite a few test runs I couldn't get any conclusive comparison results: on the same input, time varies from run to run and there seems to be no definite winner. Can someone who knows the details of the implementation tell me which should "typically" work best? Or is there something else totally different that I'm not aware of? Can it be better is I conjugate to the standard basis first?

P.S. I tried converting the matrix group action to permutations first, too, but that seems to be definitely slower.

[fingolfin]

after quite a few test runs I couldn't get any conclusive comparison results: on the same input, time varies from run to run and there seems to be no definite winner

Most likely you are seeing fluctuations due to "garbage collection": your orbit computations likely use a lot of memory and leave behind a lot of garbage. From time to time, GAP has to collect that and throw out what it doesn't need.

For reliably benchmarking, you should therefore make sure the garbage has been disposed off before starting to measure. E.g.

gap> G:=GL(18,2);; V:=GF(2)^18;;
gap> orbs:=OrbitsDomain(G,V);; time;
659

After the first run, computations get faster because GAP computed and cached some data about G. Still, timings fluctuate quite a bit:

gap> orbs:=OrbitsDomain(G,V);; time;
304
gap> orbs:=OrbitsDomain(G,V);; time;
351
gap> orbs:=OrbitsDomain(G,V);; time;
317
gap> orbs:=OrbitsDomain(G,V);; time;
352

If we instead collect garbage first, we see the "true" time, and it becomes much more consistent:

gap> CollectGarbage( true ); orbs:=OrbitsDomain(G,V);; time;
303
gap> CollectGarbage( true ); orbs:=OrbitsDomain(G,V);; time;
300
gap> CollectGarbage( true ); orbs:=OrbitsDomain(G,V);; time;
304
gap> CollectGarbage( true ); orbs:=OrbitsDomain(G,V);; time;
304

[fingolfin]

Regarding your orbit computations: if done like that, you need to deal with $2^{22} \approx 4,000,000$ vectors, each of those takes up 48 bytes:

gap> V:=GF(2)^22;
( GF(2)^22 )
gap> MemoryUsage(Zero(V));
48

That's already 192 MB just for the vectors (with additional overhead, it'll be 200 MB). That's doable but it'll put a strain on things no matter how clever you do it (reducing to your subspaces halves this, but then you also need dimension 23, so we are back to those same numbers).

The best way to optimize performance of code is to not run it at all. In this spirit I'd start by asking: do you really need all those orbits? Maybe just counting them suffices? Do you really need it for each of your many groups? If yes, can you perhaps at least try to exploit relationships between those groups? E.g. if $H < G$ then the $H$-orbits and $G$-orbits can be related (by either splitting or fusing them) which you maybe can exploit?

[alexdegt-ops]

Problem solved! In addition to "storing" the few vector spaces used, for small groups (up to 2^13) I'm computing orbit representatives via

G := List(G);
V := Filtered(V, v -> ForAll(G, g -> v*g <= v));

Once this is no longer the bottle neck, I've optimized the other part (the usage of the orbits) too, so what used to take months could be done in less than 2 days! :)

[alexdegt-ops]

Dear Max, Thanks a lot for taking your time to respond to my questions. Yes, I realize that even `List`’ing the space takes a lot of time (about half of the total used in my experiments), and apparently that’s what `OrbitsDomain(G, VectorSpace(…));` would also start with anyway (unless there are some special tricks in linear algebra that I’m not aware of; that’s why I asked it in the first place). At the end I decided to convert all actions to the standard basis (as I have to change them anyway) and have the vectors (for dim = 19..23) prestored. This seems to save some time, including on garbage collection. Memory is not an issue yet 😊 Of course, I don’t need the whole orbits, I only need representatives, but apparently there’s no way to have them without computing the whole thing. I agree with your opinion: we turn to GAP when we fail as mathematicians 😊I used this code in several related problems, and it worked reasonably well, meaning not much longer than what I used for the other Niemeier lattices. Now, it appears that it would take months, so I’m thinking about optimization. Just in case, here is the precise problem: I have a bunch of certain square 4 vectors in Leech (generating the latter over Q), and I want to find sufficiently large subcollections of rank <= 20. Being not an expert in discrete math, the smartest thing I could think of and implement is to do iterated index 2 subgroups (which eventually become index infinity as I only care about the span of a subset of the original vectors). So, now I’m trying both to optimize the subgroup computation (via orbits of the action of the symmetries on the dual space) and to reduce the repetitions during the iterations. The expected outcome is but a few subsets (half a dozen or so), but it blows up in the middle.

[alexdegt-ops]

I'm sorry for this clumsy reply. As I got it in the mail, I thought I was replying to a mail, not expecting this posted on the forum. I'll be more careful next time!

And now, when editing, I cannot get the code tag to work.