2009/12/3 javier <vengor...@gmail.com>: > 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?
YES, definitely. We really should to have way more wrapping of GAP capabilities than we currently have. William -- 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
