Not really blogging

A. Makelov

Monthly Archives: May 2012

Google Summer of Code 2012: Week 1

Hi everyone,

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 [1], 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 [1] (and maybe [2]?) 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, [1] 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 [1])? 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!

[1] 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

[2] Permutation Group Algorithms, Ákos Seress, Cambridge University Press

Advertisements

GSoC 2012: Computational Group Theory

And so it happened that by some weird accident I was accepted into GSoC 2012 to implement CGT – and Group Theory is a part of mathematics that I particularly enjoy. Until a few days ago I was pretty busy working for my exams, but in the next few weeks I should be able to start preparing for my project.

I hope that the timeline I’ve set to myself is not too impossible to do, and that I’ll be able to implement everything I promised in it.

Finally, I’d like to thank all the people that make sympy possible, and all the people that liked my application, and especially my mentor – David Joyner, and my co-mentor – Aaron Meurer, for their enthusiasm!

mathbabe

Exploring and venting about quantitative issues

Rational Altruist

Adventures of a would-be do-gooder.

Gowers's Weblog

Mathematics related discussions

What's new

Updates on my research and expository papers, discussion of open problems, and other maths-related topics. By Terence Tao

Stefan's Blog (archive, for news see blog.krastanov.org)

Most of the blog moved to blog.krastanov.org