Not really blogging

A. Makelov

Google Summer of Code 2012: Week 5

Hi everyone,

here’s a brief summary of what I’ve been doing for the fifth week of my GSoC.

  • Firstly, I finally had my first pull request merged; it’s all my fault I didn’t complain about it on the mailing list earlier : ) I had to fix a bunch of things on it (stuff like documentation using sphinx and some improvements in code quality, mainly docstrings), and now I’m really happy to have my first major contribution to sympy merged with the master branch. Thanks to everyone who helped in reviewing it – Stefan, Mario, Tom, Matthew, and of course my mentor David.
  • Secondly, my next pull request, mainly containing work from weeks 2 and 5. After some moderate rebasing over the fixes from my first pull request, it is available here. Apart from implementations of what I did in week 2, it addresses the issue of testing randomized algorithms ( which is still being discussed here ), and splits the generators for the named groups (symmetric, dihedral,…) in a separate file (which is probably going to contain more and more constructors for some well-known groups as time goes by). The PR looks longer than it is ( : ) read: any help in the review process will be appreciated), mainly because some 250 lines were copied to a new file in order to accommodate the named groups module. I hope that this time I did a better job at splitting the different parts of the PR into several commits.
  • Finally, I started work on algorithms for backtrack searches in groups. These include stuff like printing all group elements (sort of boring, but you have to start somewhere), searching for subgroups of elements satisfying a given property, finding normalizers and centralizers,  intersection of subgroups,… In general, backtrack searches tend to be slow since all the elements in the group have to be visited, but there are ways of skipping large numbers of them. Also, for some problems in computational group theory, backtrack searches are the best we have today. They are described in [1], 4.6., and I’m currently following the exposition offered there. After two days of debugging, I finally got the function PRINTELEMENTS described in 4.6.1 of [1] to work; it turned out that the current implementation of the Schreier-Sims algorithm sets the field _coset_repr of an object of class PermutationGroup in sympy.combinatorics.perm_groups.py in a way that was unexpected to me. This little digression might help anyone else trying to understand the perm_groups file better. So for example consider the following:

In [297]: S = SymmetricGroup(4)

In [298]: S.schreier_sims()

In [299]: S._coset_repr
Out[299]:
[[[0, 1, 2, 3], [1, 2, 3, 0], [2, 3, 0, 1], [3, 0, 1, 2]],
[[0, 1, 2, 3], [0, 2, 1, 3], [0, 3, 1, 2]],
[[0, 1, 2, 3], [0, 1, 3, 2]]]
 
 In [300]: S._base
Out[300]: [0, 1, 2]

From this and similar examples I concluded that the i-th component of _coset_repr is a transversal of the i-th basic orbit of the group S and tried to use this in PRINTELEMENTS. However, consired the following example:


In [302]: G = PermutationGroup([Permutation([[0, 1, 2, 3], [4], [5]]), Permutation([[1, 3], [0], [2], [4], [5]]), Permutation([[0], [1], [2], [3], [4, 5]])])

In [303]: G.schreier_sims()

In [304]: G._base
 Out[304]: [0, 1, 4]

In [305]: G._coset_repr
 Out[305]:
 [[[0, 1, 2, 3, 4, 5],
 [1, 2, 3, 0, 4, 5],
 [2, 3, 0, 1, 4, 5],
 [3, 0, 1, 2, 4, 5]],
 [[0, 1, 2, 3, 4, 5], [0, 3, 2, 1, 4, 5]],
 [[0, 1, 2, 3, 4, 5]],
 [[0, 1, 2, 3, 4, 5]],
 [[0, 1, 2, 3, 4, 5], [0, 1, 2, 3, 5, 4]]]

Here, the first two components of _coset_repr are as I expected, but the 3rd and 4th are something I didn’t expect to be there (I expected to get the 5th component instead of the 3rd, and no more components). Hence at present the behaviour of _coset_repr is not too clear to me. The current solution is to use the randomized version of the Schreier-Sims algorithm to get a base and a strong generating set. Another option would be to use the generators from the attribute _stabilizers_gens, but I haven’t tried that yet. Anyway, PRINTELEMENTS works now (edit: there are many other algorithms present for printing all the elements of a group, but this one is significant for the implementation of backtrack searches), and the order in which the elements of the group are visited (lexicographically with respect to the image of the base, in an ordering of \Omega = \{0, 1,\ldots, n-1\} in which base points come first) is used in most of the following backtrack searches, so a large part of this algorithm will be reused in subsequent algorithms ( I hope : ) ). My description of the situation assumed some knowledge of the theory behind the Schreier-Sims algorithm, so if something is not quite clear feel free to ask in the comments!

That’s it for now. Next week, I’ll continue with backtrack searches, and hopefully will implement the subgroup intersection routine (it seems formidable right now)… and put some more effort into getting the second pull request merged – I’ve got a lot to catch up with in terms of getting my code in sympy : ) .

[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

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

  1. Mario June 28, 2012 at 10:20 am

    G._coset_repr[k] gives the coset representatives of the stabilizer subgroups
    if k is in G._base; else it contains only the identity element; this make sense
    since the stabilizer subgroup which fixes all the points before k
    leaves invariant k when k is not in G._base.

    schreier_tree should be changed to agree with orbit_transversal, to
    avoid compatibility problems.

    By the way, I agree that your algorithm for orbit_transversal is faster.

    There is not currently a method to get the strong generating set,
    which is the union of G.generators and G.stabilizers_gens

    “`
    >>> def sgs(G):
    … res = G.generators
    … for h in G.stabilizers_gens():
    … h = Permutation(h)
    … if h not in res:
    … res.append(h)
    … return res
    “`

    For some groups one can compute the strong generating set
    easily without using the Schreier-Sims algorithm (e.g. in the
    direct product of groups for which the SGS is already known),
    so it should be allowed to assign it without using the Schreier-Sims algorithm.
    Maybe in the groups provided by SympPy the SGS should
    be provided, when it is easily produced, as in the case of the
    SymmetricGroup.

    Like

    • amakelov June 28, 2012 at 11:03 am

      Hi Mario,

      Thanks a lot for the clarification on the `_coset_repr` and `stabilizer_gens` attributes! I should have deduced that non-base points are just represented by the identity…
      I’m thinking about changing the interface a bit so that we have a `_strong_gens` attribute, and a public one `strong_gens`, and be able to set the strong generators from the outside (by the user) if they are known, and from the inside by our functions, when taking a direct product of groups, of constructing a known group.
      Also, I’m thinking about handling the transversal elements as a list of dictionaries, so that from `_coset_repr` we can get a list that for each basic points has keys – the elements of its basic orbit, and values – the transversal elements. This will be convenient for algorithms using the BSGS of a group.
      And about the implementation of `orbit_transversal` – it’s just the one they have in the “Handbook”🙂 I hope their other algorithms are reasonably fast as well…

      Like

  2. Pingback: Google Summer of Code 2012: Week 6 « Not really blogging

  3. Pingback: Google Summer of Code 2012: Week 7 « Not really blogging

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: