#13365: Add Semidirect Product Method for Permutation Groups
-------------------------------------------------+--------------------------
Reporter: khalasz | Owner: joyner
Type: enhancement | Status: needs_review
Priority: minor | Milestone: sage-5.3
Component: group theory | Resolution:
Keywords: groups semidirect product GAP | Work issues:
Report Upstream: N/A | Reviewers: Benjamin
Jones
Authors: Kevin Halasz | Merged in:
Dependencies: | Stopgaps:
-------------------------------------------------+--------------------------
Comment (by khalasz):
I ran some time tests on the checks. I'll leave it up to you to determine
if they are to costly (I don't think they are, but then again, I'm no more
than a novice when it comes to sage, or even CS in general).
First, I should note that my computer is kind of slow. For calibrating
purposes, see that the following process gave 31.9 ms per loop on RAB's
computer:
{{{
sage: G = DihedralGroup(2000)
sage: gens = G.gens()
sage: timeit("G == PermutationGroup(gens = gens)")
5 loops, best of 3: 127 ms per loop
}}}
Now, for the semidihedral group tests:
I didn't build actually build a semidirect product with this group, but
the following does exactly what the first test does on the calling group:
{{{
sage: G = SymmetricGroup(15)
<(1,2,6,7,5),(11,1,12,2,13,3,14,4,15,5),(6,7,8,9,10,11,1)] #this is the
end of an initialization of an 8 element list of random permutations that
generates Sym(15)
sage: len(gens)
8
sage: timeit("PermutationGroup(gens) == G")
25 loops, best of 3: 18.2 ms per loop
sage: G.order()
1307674368000
sage: PermutationGroup(gens) == G
True
}}}
The second test simply compares the length of lists using basic sage
commands, which I think is clearly not very costly (though please do tell
me if you disagree).
Finally, I have again not built a full product, but rather an isomorphism
that would be inputted into the second list of the ``mapping`` input.
Obvioulsy, this list could contain more than one isomorphism, but to
account for this we can just multiply this time by some small integer
factor.
{{{
sage:
direct_product_permgroups([c5,c5,c5,c5,c5,c5,c5,c5,c5,c5,c5,c5,c5,c5,c5,c5,c5,c5,c5,c5,c5])
sage: a
Permutation Group with generators [(101,102,103,104,105),
(96,97,98,99,100), (91,92,93,94,95), (86,87,88,89,90), (81,82,83,84,85),
(76,77,78,79,80), (71,72,73,74,75), (66,67,68,69,70), (61,62,63,64,65),
(56,57,58,59,60), (51,52,53,54,55), (46,47,48,49,50), (41,42,43,44,45),
(36,37,38,39,40), (31,32,33,34,35), (26,27,28,29,30), (21,22,23,24,25),
(16,17,18,19,20), (11,12,13,14,15), (6,7,8,9,10), (1,2,3,4,5)]
sage: a.order()
476837158203125
sage: f = [g.inverse() for g in a.gens()]
sage: alpha = PermutationGroupMorphism(a,a,f)
sage: timeit("alpha.domain() == alpha.codomain()")
625 loops, best of 3: 16.4 µs per loop
}}}
Let me know what you think.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13365#comment:7>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
