Hi Robert, On Apr 8, 2:54 pm, Robert Miller <r...@rlmiller.org> wrote: > 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. > > Seehttp://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.
I am not sure that GAP (or any other existing system) is up to day in what one can get from a modern hardware. Indeed, GAP was mainly written almost 20 years ago! At that time, e.g. the Jerrum filter algorithm was already known, but apparently disregarded, as too memory hungry. And, as we discussed at UW, many things do not need a full-blown stabiliser chain. > 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. Millerhttp://www.rlmiller.org/ -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To post to this group, send email to sage-combinat-devel@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
