In https://trac.sagemath.org/ticket/25477, we (this is mainly Moritz
Firsching) implement a new iterator for permutation groups using stabilizer
chains. Indeed, the multiplication of permutations seems to be faster than
in gap so we hope this method to be really fast in the end...
The bottleneck now is that we call
self.strong_generating_system(base)
for a permutation group self and this is done doing tons of back and forth
translations between sage and gap using the pexpect interface (if I
understand it correctly).
I now have reimplemented the computation of the strong generating system
directly in gap, and now the remaining bottleneck is to turn the gap
permutations back to sage permutations. So my question is
What is the currently fastest way to turn gap permutations into sage
permutations?
Here is the code:
#############################
def SGS_old(G): # taken from strong_generating_system
sgs = []
stab = G
base = G.base()
for j in base:
sgs.append(stab.transversals(j))
stab = stab.stabilizer(j)
return sgs
def SGS_new(G, gap_output=True):
S = G._gap_().StabChain()
gap.execute(gap_cosets)
cosets = S.CosetsStabChain()
if gap_output:
return cosets # <-------
elt_class = G._element_class()
gap2sage = lambda elt: elt_class(elt, G, check=False)
return [ [ gap2sage(elt) for elt in coset] # <-------
for coset in cosets ] # <-------
gap_cosets = """CosetsStabChain := function ( S )
local cosets, # element list, result
new_coset, #
pnt, # point in the orbit of <S>
rep; # inverse representative for that point
# if <S> 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;
"""
#############################
and here is the test case to look at:
#############################
sage: 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: %time XX = SGS_old(A)
CPU times: user 3.67 s, sys: 664 ms, total: 4.34 s
Wall time: 4.45 s
sage: %time XX = SGS_new(A, True)
CPU times: user 4.94 ms, sys: 712 µs, total: 5.65 ms
Wall time: 14 ms
sage: %time XX = SGS_new(A, False)
CPU times: user 2.48 s, sys: 116 ms, total: 2.59 s
Wall time: 2.61 s
#############################
so the actual strong generating system is computed very fast in gap in
SGS_new(A, True) while casting the output into sage in SGS_new(A, False)
then takes forever.
Thanks for your help -- I would expect this fast iteration will help not
help my code to be faster!
Christian
--
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.
