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@gap-system.org
https://mail.gap-system.org/mailman/listinfo/forum
