[GAP Forum] GAP behaviour for large integers

[Sanchez Garcia R.]

Thank you Dmitrii.

I have tried finding small generators for each permutation group, but finding them takes as long as just computing the orbits in the original group (code below). 

Listing all integers in advance won’t help either, as most integers 1 to n will appear as generators. 

The code I have used is
#produce small generators
mp := MovedPoints(gens);;
l := Length(mp);;
p := ();;
for i in [1..l] do
	if mp[i] > l then
		p := p * (i,mp[i]);;
	fi; 
od;
gens := OnTuples(gens,p);;

Is there a more efficient way of finding small generators? Or just telling GAP to treat them as symbols rather than actual (very large) integers?

Alternatively, does anyone know an alternative software to GAP that can perhaps handle permutation groups generated by large integers more efficiently? 

Many thanks,
Ruben


> On 26 Mar 2018, at 23:14, dmitrii.pasechnik at cs.ox.ac.uk wrote:
> 
> 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