In another thread (finite complex reflection groups and matrices over the universal cyclotomic field), Christian wrote: > - is there a Sage implementation of permutation groups, or only the > gap implementation (it takes very long to go through the elements of a > permutation group, even in small examples)?
Dima wrote: > ...GAP is very quick in enumerating the elements of a permutation group > (it has a highly optimized code written in C to do the sorts of things > related to permutation groups)... I've spent a lot of time looking at that source code lately. The permutation group elements themselves as well as their arithmetic is written in C (i.e. is in the GAP kernel). However, the stabilizer chain algorithms are written in the GAP language, which is an interpreted language. These algorithms would be faster written in a compiled language like Cython. Dima also wrote: > There is an ongoing project to speed this up in a serious way, so > circumvent the use of IPC by creating a libGAP. > See http://trac.sagemath.org/sage_trac/ticket/6391 > You are welcome to try helping with it if you have time. The aim of this project is much more ambitious than just speeding up permutation groups, as Dima knows. However, GAP can be very slow at some very basic computations. See for example #10976. This isn't due to the fact that the permutation group code in GAP isn't very sophisticated, because it certainly is. But some of it is not used as well as it could be. Also, after a certain cutoff, GAP uses Monte Carlo algorithms, which actually means that the results are not provably correct, just very very probably so. I have not yet checked whether this has a bearing on whether Sage's proof=True option is incorrect somewhere, but it is possible. Tom wrote: > Robert Miller has been hard at work implementing stabilizer chains for > permutation groups (see #10804). It should be fairly easy to > enumerate iterate over the elements of a permutation group, fully > within Cython, if that was your desire. Eventually, it'd be nice to > have the PermutationGroup class use Robert's code by default. Emphasis on eventually. I plan on spending a lot of time in the future looking at GAP code, Jeffrey Leon's code, and other sources to try to make a top-notch permutation group library, but nobody should hold their breath. This will take a long time and a lot of hard work. The algorithms in GAP took years to establish, and people have written many papers and several books on the work done to get these algorithms right. The work in #10804 is more of a proof of concept and an intermediate tool to get canonical augmentation off the ground than finished product. -- Robert L. Miller http://www.rlmiller.org/ -- 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
