Google Summer of Code 2012: Week 1
May 26, 2012Posted by on
Here is a brief summary of what I’ve been doing for the first six days of my GSoC.
Since there was already some work done on computational group theory in the module sympy.combinatorics, mainly in the files perm_groups.py and permutations.py, I got to know what the code is doing and made some minor improvements (improved docstrings, removed some duplicate functionality.) In particular, the implementation of the Schreier-Sims algorithm took most of my time, and I still have to analyze its complexity (it seems a bit slow). Anyway, I found the following files particularly useful in making my way through the code.
Since there were already a lot of things implemented, this interfered with the schedule I had set for myself on my GSoC application. So after a quick change of plans, I decided to:
- implement constructors for four of the basic types of groups (symmetric, cyclic, dihedral, alternating) in order to be able to use groups of fairly large size for testing and comparing the complexity of the different algorithms for computation with groups
- Evaluate the more basic functionality already implemented (read: all but Schreier-Sims), in particular at orbits and stabilizers. It turned out that the implementations currently in sympy are slower than the ones suggested in , so I rewrote these and added implementations for the Schreier vector and some other orbit-related computations.
In the near future (today and tomorrow), I’ll implement a procedure for taking direct products of several groups (so that I can have even more examples of groups for testing and playing around) and Monte Carlo testing if a given permutation group is large (the symmetric or the alternating group). You’re welcome to take a look at my branch labeled week1, and I’ll do a pull request in the next couple of days.
In the more distant future, I’ll dive into Schreier-Sims and take a look at the implementation offered in  (and maybe ?) in order to try to compare it with the existing one. Also, the randomized version of Schreier-Sims (the output of which can then be quickly tested with the deterministic version,  says) is promised to be significantly faster so it is a must-have. And I feel that there is some more optimization that can be done in permutations.py and perm_groups.py.
And about the changes in the interface I wanted to implement – my main pain right now is that singleton cycles have to be included in the cyclic form of a permutation. But the cyclic form itself is not heavily used in the rest of the functionality, so it is not such a pressing issue. Also, I feel that possible changes in the interface need some more careful thinking on my part… Do we want our group action to be on the left or on the right (GAP and MAGMA do it on the right, as I gather from )? Do we want to label the underlying set for a permutation by 0,1,…, n-1 or 1,2,…,n?…
Anyway, I’m really enthusiastic about my project and hope that we’ll have some nice and reasonably fast algorithms in CGT by the end of the summer!
 Derek F. Holt, Bettina Eick, Bettina, Eamonn A. O’Brien, “Handbook of computational group theory”, Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, FL, 2005. ISBN 1-58488-372-3
 Permutation Group Algorithms, Ákos Seress, Cambridge University Press