Google Summer of Code 2012: Week 13
August 20, 2012
Posted by on
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], ]), 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
__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!