[GAP Forum] GAP behaviour for large integers

[Sanchez Garcia R.]

Dear Forum,

I am using gap for some simple calculations (e.g. orbits) on very small permutation groups generated by (relatively) large integers (representing vertices in very large networks). For example:
gap> Orbits((n1 n2), (n3 n4));
where n1,…,n4 are integers between 1 and n. (I need to run this command many times over a very long list.)

The time it takes to run this command depends on n: for n about 20,000 I can process 1,700 orbits per second, but when n is about 300,000 it drops to 160 orbits per second. A full calculation (for n=5,189,808) that should take about 6 minutes at top speed, takes me about 11 hours to complete.

For a minimal working example, try
gap> n:=10^k;; Orbits(Group([(n,n+1),(n+1,n+2)]);; time;
As k goes from 5 to 8, time returns 0, 3, 22, and 337.

Mathematically, the group Group((1,2),(3,4)) is isomorphic to Group((10000,20000),(30000,40000)) but gap finds it much harder to deal with the latter, I suppose because of the internal representation as a subgroup of SymmetricGroup(40000).

I want to tell gap that n1, n2, n3, n4 are just ‘labels’ rather than actual integers between 1 and n (very large)? Is there an obvious way of doing that? Of course there could be repetitions e.g. n2==n3. I have tried a few things e.g. finding smaller/equivalent generators but there is always a bottleneck somewhere.

Apologies for the long email, and many thanks in advance for any help.

Best wishes,
Ruben
--
Dr Ruben Sanchez-Garcia
Lecturer in Pure and Applied Mathematics
Faculty of Social, Human and Mathematical Sciences
University of Southampton

#This is the actual code I run
Read(“generators");; #read gen (a very long list of permutations)
Read(“geomdecomp");; #read index (a very long list of integers)
factor_num := 0;;
orbits := [];;
for gen in [1..Maximum(index)] do
factor_num := factor_num + 1;;
pos := Positions(index,gen);
H := Group(gens{pos});
orbits[factor_num] := Orbits(H);
od;