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.