Here is a brief summary of what we did in the second and third week of GSoC.
First of all I got late in blogging about our progress for the weeks 2, 3. Since the internet connection was disrupted(reason) for almost 3 weeks in my city, so in between I had to move out to some other place. But still project progress is good :)
- PR #11140 on implementation of strategies of coset enumeration has been merged.
We implemented the Coset Enumeration strategies. Suppose $G$ is defined by a finite presentation, and $H$ is a subgroup of $G$ (for $H$ we currently only list of generators which generate $H$), which is specified by words in the generators of $G$ that generate $H$. The procedure is known as coset enumeration and is one of the most fundamental methods in CGT. No algorithm (its been proved mathematically ) can be guaranteed to terminate for coset enumeration, so it can’t be defined to have a fixed complexity.
Coset Table is equivalent to the permutation representation of the input group $G$ in its action by right multiplication on the right cosets of $H$. Beginning with the
Coset Table, we have initialised it with various attributes in SymPy, most of them are instances of
list, they are appended on the way while strategies like HLT, Felsch run over it. Contrary to what I mentioned in my last post,
CosetTable is not a subclass of
The algorithm we have implemented is known as Todd Coxeter algorithm. The algorithm can use too much memory and time, but still memory is more important resource than time in this algorithm. This algorithm has got two major implementations:
In this strategy whenever we use the
C.scan_and_fill($\alpha$, $w$)for scanning the word $w$ over coset $\alpha$, routine for scanning which if the scan is incomplete makes a new definition of coset using
definethen we make new definitions to enable the scan to complete; that is, we fill in the gaps in the scan of the relator or subgroup generator. Kalevi suggested to make some modification from the original pseudo-code, which resulted in quite a few improvements, since the changes removes un-necessary scanning.
For calculating the index of , for a generator , we initialised the Coset Table with a dictionary
A_dict_inv, which has
>>> for x, index in self.A_dict.items(): ... if index % 2 == 0: ... self.A_dict_inv[x] = self.A_dict[x] + 1 ... else: ... self.A_dict_inv[x] = self.A_dict[x] - 1
We changed the slicing of the Free Group elements, which now work this way.
>>> w = x**2*y**6 >>> w x >>> w y
Since earlier it was only possible using the
.subword(i, i+1) to obtain the “word”.
We have now completed the PR #11140. We used the utf-8 encoding in
sympy/combinatorics/fp_groups.py in its comments, which was generating the error in
Python2.7 but not in
SyntaxError: Non-ASCII character '\xce' in file /home/gaurav/Public/sympy/sympy/combinatorics/fp_groups.py on line 79, but no encoding declared; see http://www.python.org/peps/pep-0263.html for deta
and then using the line
# -*- coding: utf-8 -*- at the top of file resolved the issue, so seems like
Python2.x is more sensitive to such issues.
There was one error in the implemted code:
>>> from sympy.combinatorics.free_group import free_group >>> from sympy.combinatorics.fp_groups import FpGroup, coset_enumeration_r, CosetTable >>> F, x, y = free_group("x, y") >>> f = FpGroup(F, [x**2, y**3, (x*y)**3]) >>> Y = [x*y] >>> C = coset_enumeration_r(f, Y) >>> C.table # this will return the table
As for refinement, I will paste another one.
# these are the steps that happen internally >>> C = CosetTable(f, Y) >>> C.scan_and_fill(0, x*y) >>> C.scan_and_fill(0, x**2) >>> C.scan_and_fill(0, y**3) >>> C.scan_and_fill(0, (x*y)**3) # till now coset table is fine. # here the coset table returned is wrong.
In the implementation of
scan_and_fill the implemened code differed from that in the book in one significant aspect. In the book,
scan_and_fill looped until it filled the $\alpha$ row in the table. (“Made a new definition and continue with scan.”). While the implemented code returned after one definition, the error occured since I tried removing the while loop (some testing purpose). Then we also added some “examples” from .
In this we first find the first undefined coset $\alpha$, in this instead of seeing ahead by making use of
lookahead, we make deductions, which are put in a
list instance which behaves a stack), which contains the pair $(\alpha, x)$, whenever a new definition or a deduction is made, this reduces the number of un-necessary cosets made (loweing the memory use at the cost of time).
Though we have made use of
CosetTableDefaultMaxLimit = 409600 (similar to that in GAP), till now I haven’t found a single example which would exhaust this much memory in our implementation, every one just seems to take too much of time.
Python utilities learned on the way:
- At one point we had to make a list of generator and inverse of generators of a finitely presented groups i.e `A` for a `CosetTable`, I did a bit of searching a arrived at using the [chain.from_iterable](https://docs.python.org/2/library/itertools.html#itertools.chain.from_iterable)</a> from the `itertools` which works as follows: ``` >>> from itertools import chain >>> list(chain.from_iterable((x**2, x**3) for x in range(4))) [0, 0, 1, 1, 4, 8, 9, 27] ```
- Use of `product` routine, since in `coset enumeration`, we often iterate over $w \in Y$ and $x \in A$.
- In `Python2.x` a `list` instance doesn't have a `copy` attribute, so `list()` function or slicing is used to make a shallow copy. 
At the end of the post, here’s one awesome small example of
coset enumeration using the HLT strategy. Here is how the code works!! :)
In: from sympy import * In: from sympy.combinatorics.free_group import free_group In: from sympy.combinatorics.fp_groups import FpGroup, CosetTable, coset_enumeration_r In: F, x, y = free_group("x, y") In: f = FpGroup(F, [x**2, y**3, (x*y)**4]) In: C = coset_enumeration_r(f, [x]) In: C.table Out:[[0, 0, 1, 2], [3, 3, 2, 0], [6, 6, 0, 1], [1, 1, 4, 10], [5, 5, 10, 3], [4, 4, 6, 7], [2, 2, 7, 5], [8, 8, 5, 6], [7, 7, 9, 12], [10, 10, 12, 8], [9, 9, 3, 4], [None, 10, 12, None], [12, 12, 8, 9], [None, 12, 8, 9], [7, None, None, 13]] In: C.compress() In: C.standardize() In: C.table Out: [[0, 0, 1, 2], [3, 3, 2, 0], [4, 4, 0, 1], [1, 1, 5, 6], [2, 2, 7, 8], [8, 8, 6, 3], [9, 9, 3, 5], [10, 10, 8, 4], [5, 5, 4, 7], [6, 6, 11, 10], [7, 7, 9, 11], [11, 11, 10, 9]]
My mentor, Kalevi, has been very much supportive, when I informed him about my possible abscence (due to internet unavailability), he even sent me a mail about the things we could do next, even if I am offline. So here they are: Cosets in Permutation Groups, Finitely presented abelian groups.
- 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-5848-372-3 .
- 2. John J. Cannon, Lucien A. Dimino, George Havas and Jane M. Watson, Implementation and Analysis of the Todd-Coxeter Algorithm
- 3. https://mail.python.org/pipermail/tutor/2006-November/051189.html
- 4. http://www.gap-system.org/Manuals/doc/ref/chap47.html