Hi all, I have been lately doing some work that required me to explicitly compute conjugacy classes of certain finite groups.
Since in sage there is no built-in function for that I defined my own in the obvious straight-forward way: sage: def conjugacy_class(g,G): ... cc = Set([x*g*x^(-1) for x in G]) ... return cc this feels very pythonic and works just fine, but is terribly inefficient since it requires a lot of computations and stores in memory an array of the whole size of the group G before deleting duplicates. As GAP has a function for computing the conjugacy class of an element, I decided to wrap it and compare it with the naive implementation above, coming up with this: def conjugacy_class_gap(g,G): ... GG = G._gap_() ... gg = g._gap_() ... cc = GG.ConjugacyClass(gg).AsList().sage() ... return Set([G(x) for x in cc]) the coercions in the last line produce a bit of overhead, but are necessary to be sure that I get a working sage object once I am done. Even with that extra overhead, the time difference between the two functions is quite noticeable, GAP being about 20x faster than naive for small groups: sage: %time sage: G = SymmetricGroup(6) sage: g = G((1, 2, 3, 4, 5, 6)) sage: c1 = conjugacy_class(g,G) CPU time: 0.96 s, Wall time: 1.18 s sage: %time sage: G = SymmetricGroup(6) sage: g = G((1, 2, 3, 4, 5, 6)) sage: c2 = conjugacy_class_gap(g,G) CPU time: 0.05 s, Wall time: 0.08 s stays so when the group gets larger: sage: %time sage: G = SymmetricGroup(7) sage: g = G((1, 2, 3, 4, 5, 6)) sage: c1 = conjugacy_class(g,G) CPU time: 6.99 s, Wall time: 8.45 s sage: %time sage: G = SymmetricGroup(7) sage: g = G((1, 2, 3, 4, 5, 6)) sage: c2 = conjugacy_class_gap(g,G) CPU time: 0.32 s, Wall time: 0.36 s and for really large groups gets even bigger, in this case is over 100x faster (WARNING, the first test takes about 10min to complete): sage: %time sage: G = SymmetricGroup(9) sage: g = G((1, 2, 3, 4, 5, 6)) sage: c1 = conjugacy_class(g,G) CPU time: 529.72 s, Wall time: 618.07 s sage: %time sage: G = SymmetricGroup(9) sage: g = G((1, 2, 3, 4, 5, 6)) sage: c2 = conjugacy_class_gap(g,G) CPU time: 3.87 s, Wall time: 4.66 s Observe that the two functions produce exactly the same object: sage: c1 == c2 True My question: would it be interesting to include the wrapper for the GAP function in sage? Cheers Javier -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
