solving the x's and y's of math, programming and life

GSoC 2016 Week 2, 3

Jun 14, 2016 • Gaurav Dhingra

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 :)

Status update:

  • PR #11140 on implementation of strategies of coset enumeration has been merged.

</p>

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 [4]) 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 list.

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:

HLT strategy

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 define then 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 \(x^{-1}\), for a generator \(x\), we initialised the Coset Table with a dictionary A_dict_inv, which has (gen,index) as (key,value) pair.

>>> 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[1]
x
>>> w[3]
y

Since earlier it was only possible using the .subword(i, i+1) to obtain the \(i{th}\) “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 Python3.4.

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 [2].

Felsch strategy

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 deduction_stack (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). </p>

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. [3]

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[1]: from sympy import *
In[2]: from sympy.combinatorics.free_group import free_group
In[3]: from sympy.combinatorics.fp_groups import FpGroup, CosetTable, coset_enumeration_r
In[4]: F, x, y = free_group("x, y")
In[5]: f = FpGroup(F, [x**2, y**3, (x*y)**4])
In[6]: C = coset_enumeration_r(f, [x])
In[7]: C.table
Out[7]:[[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[8]: C.compress()
In[9]: C.standardize()
In[10]: C.table
Out[10]: [[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.

References

  • 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

</body> </html>