Not really blogging

A. Makelov

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

5 responses to “Google Summer of Code 2012: Week 1

  1. Aaron Meurer May 26, 2012 at 6:34 pm

    Regarding your branch, you’re going to need to start writing better commit messages. A message like “same” isn’t very informative, and won’t really help someone if they come across your commit in the future (e.g., through git bisect or git blame). In fact, you’ll probably want to go back and fix the ones you have at some point (I’ll show you how to do this).

    Like

  2. amakelov May 26, 2012 at 6:43 pm

    At the time I was writing the commit message I was aware that it’s not very helpful but now I see that the implications of this can be worse than I expected… I’m sorry about that and I’ll try to be more careful in the future. And, yes, it’d be nice if I could fix them🙂

    Like

  3. Dima May 27, 2012 at 9:28 am

    Hi, I noticed few omissions on your schedule regarding permutation groups: that is: testing transitive groups for primitivity (and computing blocks of an imprimitivity system), and computing actions of permutation groups on various things, like subsets, etc. Both these things are very quick (and they don’t need a strong generating system) and very useful. The first one is a good first step towards recognition of transitive groups.
    As well, it might be great to connect it to some graph automorphism functionality.

    Like

  4. amakelov May 27, 2012 at 2:45 pm

    Testing for primitivity and computing block systems appears later on in my proposed timeline (I myself am not quite sure for what exact reason🙂 ), but yes, these algorithms can definitely be implemented without a strong generating set, in particular there is a discussion of Atkinson’s algorithm in [1] that should be helpful.

    Computing actions on subsets also seems doable (I assume you mean actions on block systems? Or do you mean restricting the permutation group to some subset of the points it’s acting on?).

    And graph-theoretical functionality would also be fun to implement, especially since it seems that my timeline won’t take as long as I thought.

    Like

  5. amakelov May 28, 2012 at 7:24 am

    I rebased my branch, wrote a better commit message and did a pull request: https://github.com/sympy/sympy/pull/1319

    All tests passed a couple of minutes ago, so everyone interested is welcome to review!

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

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

%d bloggers like this: