[GAP Forum] GAP behaviour for large integers

[Sanchez Garcia R.]

Thank you Dmitrii.

I tried your suggestion but the replacement of generators takes at least as long as computing the orbits in the original permutation group (code below). 

Listing all the integers before the permutation won’t help either, as most integers 1 to n appear at least once. 

This is what I tried:
#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 computationally efficient way of finding small generators? If anyone knows it’d be grateful. 

Alternatively, is there a more efficient mathematical software than GAP to deal with (small) permutation groups generated by large integers? I only use Orbits() and IsNaturalSymmetricGroup(). 

Best wishes,
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