[GAP Forum] GAP behaviour for large integers

[dmitrii.pasechnik at cs.ox.ac.uk]

Dear Ruben,

So you have very sparse permutation groups.

can't you just list all the integers, say you have k distinct ones, n_1, n_2,..., n_k, for each orbit computation, 
replace generators your generators with the ones from Sym(k), do the computation, and
read the result back?

The listing of integers most probably can be done before you create your
permutations, as they come from somewhere, after all, instead of
changing the permutations with large numbers you already have.

Best,
Dmitrii

On Mon, Mar 26, 2018 at 05:12:17PM +0000, Sanchez Garcia R. wrote:
> 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;
> 
> _______________________________________________
> Forum mailing list
> Forum at gap-system.org
> https://mail.gap-system.org/mailman/listinfo/forum