[sage-devel] Re: Permutation group: faster use of stabilizer chain from gap

[Christian Stump]

Okay, I think I got all the bottlenecks resolved now -- I'd appreciate 
further comments and reviews on the ticket (https://trac.sagemath.org/
ticket/25477 ), especially from 
someone familiar with the libgap interface.

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] Re: Permutation group: faster use of stabilizer chain from gap

[Christian Stump]

Hi,

Thanks for the reply! The ticket has evolved drastically since my post here 
(and indeed uses libgap now), the bottleneck now is that I have a libgap 
list of libgap integers (which are indeed C integers) and need to use these 
in cython, which I currently fail to do.

Anyway, I do not see how your answer would improve the situation even in 
the beginning because I see that the previous
SGS_new(A,True)
is faster than
SGS_libgap(A,True)
and you do not provide a way to then turn the libgap lists into sage lists, 
and this takes all the time in the computation. Or am I overseeing 
something and I can get this output directly into sage?

Here is the new code
def SGS_new(self, gap_output=True):
gap_cosets = libgap.function_factory("""function (G)
local   S0,
CosetsStabChain;

S0 := StabChain(G);
CosetsStabChain := function(S)  # for the recursive call
local   cosets, # element list, result
new_coset,  # new coset computed along the way
pnt,# point in the orbit of 
rep;# inverse representative for that point

# if  is trivial then it is easy
if Length(S.generators) = 0  then
cosets := [ [S.identity] ];

# otherwise
else

# compute the elements of the stabilizer
cosets := CosetsStabChain( S.stabilizer );

# loop over all points in the orbit
new_coset := [];
for pnt  in S.orbit  do

# add the corresponding coset to the set of elements
rep := S.identity;
while S.orbit[1] ^ rep <> pnt  do
 rep := LeftQuotient( S.transversal[pnt/rep], rep );
od;
Add( new_coset, rep );
od;
Add( cosets, new_coset );
   fi;

   # return the result
   return cosets;
   end;
   return CosetsStabChain(S0);
end;""")
G = libgap.Group(self.gens())
cosets = gap_cosets(G)
# the following case from the gap permutation elt to a
# sage permutation is much too slow -- stumpc5, 2018-06-05
one = self.one()
gap2sage = lambda elt: one._generate_new(libgap.ListPerm(elt).sage())
if gap_output == 1:
return cosets
elif gap_output == 2:
return [[elt for elt in coset] for coset in cosets]
elif gap_output == 3:
return [[[ i.sage() for i in libgap.ListPerm(elt)] for elt in coset] 
for coset in cosets]
elif gap_output == 0:
gap2sage = lambda elt: libgap.ListPerm(elt).sage()
return [ [ gap2sage(elt) for elt in coset] for coset in cosets ]

As you can see
sage: p = [(i,i+1) for i in range(1,601,2)]
sage: q = [tuple(range(1+i,601,3)) for i in range(3)]
sage: A = PermutationGroup([p,q])
sage: A.cardinality()

sage: %time XX =  SGS_new(A,1)
CPU times: user 58.4 ms, sys: 60 µs, total: 58.4 ms
Wall time: 58.5 ms
sage: %time XX =  SGS_new(A,2)
CPU times: user 48.1 ms, sys: 75 µs, total: 48.2 ms
Wall time: 48.1 ms
sage: %time XX =  SGS_new(A,3)
CPU times: user 296 ms, sys: 3.95 ms, total: 300 ms
Wall time: 299 ms
sage: %time XX =  SGS_new(A,0)
CPU times: user 264 ms, sys: 79 µs, total: 264 ms
Wall time: 263 ms


As you can see, all the time is spent in translating thousands of gap ints 
into sage ints (and lists of these, but that seems fast). Help is still 
appreciated!

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] Re: Permutation group: faster use of stabilizer chain from gap

[Simon Brandhorst]

Use libgap:

sage: def SGS_libgap(G, gap_output=True):
: S = libgap(G).StabChain()
: libgap.eval(gap_cosets)
: cosets = S.CosetsStabChain()
: if gap_output:
: return cosets
: 

sage: %time XX = SGS_libgap(A,True)
CPU times: user 31.7 ms, sys: 59 µs, total: 31.8 ms
Wall time: 31.9 ms
sage: %time XX = SGS_libgap(A,False)
CPU times: user 31.7 ms, sys: 59 µs, total: 31.8 ms
Wall time: 31.8 ms


sage: %time XX = SGS_old(A)
CPU times: user 3.43 s, sys: 535 ms, total: 3.96 s
Wall time: 4.03 s
sage: %time XX = SGS_new(A,True)
CPU times: user 3.39 ms, sys: 2.03 ms, total: 5.41 ms
Wall time: 7.98 ms
sage: %time XX = SGS_new(A,False)
CPU times: user 2.44 s, sys: 101 ms, total: 2.54 s
Wall time: 2.59 s




-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.