Not really blogging

A. Makelov

Monthly Archives: August 2012

Google Summer of Code 2012: Week 13

Hi all, here’s a brief summary of my 13th (and last) week of GSoC.

  • I continued my work on centralizers, improving normal closure, derived in lower central series, etc. My most recent pull request containing these additions just got merged and can be found here. This week I spent a lot of time on writing better tests and developing some new test practices. The group-theoretical algorithms in the combinatorics module are getting more and more complicated, so better, cleverer and more thorough tests are needed. I came up with the following model for verification:
    – since the results of the tests are very hard to compute by hand, some helper functions are needed that find the wanted object in a brute-force manner using only definitions. For example, we often look for a subgroup with certain properties. The most naive and robust approach to this is to:
    – list all group elements, go over the list and check each element for the given property.
    – Then, make a list of all the “good” elements and compare it (as a set) with the list of all elements of the group the function being tested returns.
    Hence, a new file was created, sympy/combinatorics/testutil.py, that will host such functions. (Needless to say, they are exponential in complexity, and for example going over all the elements of SymmetricGroup(n) becomes infeasible for n larger than 10.)
    – The presence of functions being used to test other functions gets us in a bit of a Quis custodiet ipsos custodes? situation, but this is not fatal: the functions in testutil.py are extremely straightforward compared to the functions in perm_groups.py that they test, and it’s really obvious what they’re doing, so it’ll take less tests to verify them.
    – In the tests for the new functions from perm_groups.py, I introduced some comments to indicate what (and why) I’m testing. Another practice that seems to be good is to verify the algorithms for small groups (degrees 1, 2, 3) since there are a lot of corner cases there that seem to break them.
  • I started work on improving the disjoint cycle notation, namely excluding singleton cycles from the cyclic form; however, there are other changes to handling permutations that are waiting to be merged in the combinatorics module here, so I guess I’ll first discuss my changes with Christopher. Currently, I see the following two possibilities for handling the singleton cycles:
    – add a _size attribute to the Permutation class, and then, when faced with something like Permutation([[2, 3], [4, 5, 6], [8]]), find the maximum index appearing in the permutation (here it’s 8) and assign the size of the permutation to that + 1. Then it remains to adjust some of the other methods in the class (after I adjusted mul so that it treats permutations of different sizes as if they leave all points outside their domain fixed, all the tests passed) so that they make sense with that new approach to cyclic forms.
    – more ambitious: make a new class, ExtendedArrayForm or something, with a field _array_form that holds the usual array form of a permutation. Then we overload the __getitem__ method so that if the index is outside the bounds of self._array_form we return the index unchanged. Of course, we’ll have to overload other things, like the __len__ and __str__ to make it behave like a list. Then instead of using a list to initialize the array form of a permutation, we use the corresponding ExtendedArrayForm. This will make all permutations behave as if they are acting on a practically infinite domain, and if we do it that way, we won’t have to make any changes to the methods in Permutation – everything is going to work as expected, no casework like if len(a) > len(b),... will be needed. So this sounds like a rather elegant approach. On the other hand, I’m not entirely sure if it is possible to make it completely like a list, and also it doesn’t seem like a very performance-efficient decision since ExtendedArrayForm instances will be created all the time. (see the discussion here).
  • Still nothing on a database of groups. I looked around the web for a while but didn’t find any resources… the search continues. Perhaps I should ask someone more knowledgeable.

That’s it for now, and that’s the end of my series of blog posts for the GSoC, but I don’t really feel that something has ended since it seems that my contributions to the combinatorics module will continue (albeit not that regularly : ) ). After all, it’s a lot of fun, and there are a lot more things to be implemented/fixed there! So, a big “Thank you” to everyone who helped me get through (and to) GSoC, it’s been a pleasure and I learned a lot. Goodbye!

 

Advertisements

Google Summer of Code 2012: Week 12

Hi all, here’s a brief summary of the 12th week of my GSoC:

  • Centralizers got some more attention since there were several bugs in the implementation from last week; this also exposed a bug in .subgroup_search() as it is on sympy/master right now. Fortunately, I located it and fixed it earlier today, so the fix for .subgroup_search() will be contained in my next pull request. In fact, it is just three more lines that should be added. Namely,
    # line 29: set the next element from the current branch and update
    # accorndingly
    c[l] += 1
    element = ~(computed_words[l - 1])
    

    should be replaced with

    # line 29: set the next element from the current branch and update
    # accorndingly
    c[l] += 1
    if l == 0:
        element = identity
    else:
        element = ~(computed_words[l - 1])
    

    since we might be at the bottom level with l=0. In this case, python doesn’t yell at you for looking up computed_words[-1] since negative indices wrap around the list in python. Yet another silly mistake that’s incredibly hard to track down! I hope that it will work properly from now on, and I’ll have to include some more tests to it.

  • The description of the algorithm for finding the center in polynomial time given in [1] didn’t really make sense to me, so instead a straightforward one,
    def center(self):
        return self.centralizer(self)
    

    was used. This can be updated later when I (or someone else) figures out the polynomial-time algorithm.

  • A new, faster algorithm for finding normal closures: this one uses the incremental version of Schreier-Sims, and some randomization. It’s described in [1].
  • Some applications of normal closure: the derived series, lower cenral series, the commutator of two subgroups of a group, nilpotency testing. Now we have things like this:
    In [68]: from sympy.combinatorics.named_groups import *
    In [69]: S = SymmetricGroup(4)
    In [70]: ds = S.derived_series()
    In [71]: len(ds)
    Out[71]: 4
    In [72]: ds[1] == AlternatingGroup(4)
    Out[72]: True
    In [73]: ds[2] == DihedralGroup(2)
    Out[73]: True
    In [74]: ds[3] == PermutationGroup([Permutation([0, 1, 2, 3])])
    Out[74]: True
    

    demonstrating the well-known normal series of groups e < K_4 < A_4 < S_4 that solves the symmetric group on 4 letters. Note that the normal closure algorithm was already there thanks to the work of Mario, I just improved it a bit and added some applications.

  • Moved DirectProduct() to a new file, group_constructs.py, that is planned to hold functions that treat several groups equally (for one other example, the commutator of two groups in the full symmetric group) rather than treating them in some sort of subgroup-supergroup relationship (such as .centralizer()).

I wrote docstrings for the new stuff, and my current work can be found on my week10 branch. There will be some comprehensive test following the new additions (and I’ll need GAP to verify the results of some of them, probably). It seems that Todd-Coxeter won’t happen during GSoC since there’s just one more week; instead, I plan to focus on improving disjoint cycle notation and group databases.

[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

Google Summer of Code 2012: Week 11

Hi all, here’s a brief summary of the 11th week of my GSoC.

  • Yay! Subgroup searching now works with the use of .stabilizer(), as I discussed in my previous blog post. Surprisingly, the running time is similar to that of the flawed version using .baseswap() (whenever the one using .baseswap() works), you can play around with the two versions on my week6 (has a bug, using .baseswap()) and week9 (seems to work, using .stabilizer()) branches.
  • Consequently, I made a new pull request containing the incremental version of Schreier-Sims, the remove_gens utility for getting rid of redundant generators in a strong generating set, and the new (working) subgroup_search algorithm. You’re most welcome to help with the review!
  • I worked on several applications of subgroup_search() and the incremental Schreier-Sims algorithm. Namely, the pointwise stabilizer of a set of points (via the incremental Schreier-Sims algorithm):
In [4]: from sympy.combinatorics.named_groups import *
In [5]: A = AlternatingGroup(9)
In [6]: G = A.pointwise_stabilizer([2, 3, 5])
In [7]: G == A.stabilizer(2).stabilizer(3).stabilizer(5)
Out[7]: True

(this is much faster than the naive implementation using .stabilizer() repeatedly), and the centralizer of a group H inside a group G:

In [11]: from sympy.combinatorics.named_groups import *
In [12]: S = SymmetricGroup(6)
In [13]: A = AlternatingGroup(6)
In [14]: C = CyclicGroup(6)
In [15]: S_els = list(S.generate())
In [16]: G = S.centralizer(A)
In [17]: G.order()
Out[17]: 1
In [18]: temp = [[el*gen for gen in A.generators] == [gen*el for gen in A.generators] for el in S_els]
In [19]: temp.count(False)
Out[19]: 719
In [20]: temp.count(True)
Out[20]: 1
In [21]: G = S.centralizer(C)
In [22]: G == C
Out[22]: True
In [23]: temp = [[el*gen for gen in C.generators] == [gen*el for gen in C.generators] for el in S_els]
In [24]: temp.count(True)
Out[24]: 6

(it takes some effort to see that these calculations indeed prove that .centralizer() returned the needed centralizer). The centralizer algorithm uses a pruning criterion described in [1], and even though it’s exponential in complexity, it’s fast for practical purposes. Both of the above functions are available (albeit not documented yet) on my week10 branch.

  • The next steps are an algorithm for the centre in polynomial time, and an algorithm to find the intersection of two subgroups! And after that, I hope to be able to implement the Todd-Coxeter algorithm…

That’s it for now!

[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

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