GSoC Week 7

Jul 11, 2016 • Gaurav Dhingra

Hi everyone.

Here’s what we have been doing for 7th week of GSoC.

Kalevi mentioned about the $LaTex$ not getting rendered on Planet Sympy website, thought it works fine on my website. Following the conversation Aaron opened issue planet-sympy/issues/45, though it hasn’t been fixed.

This week we completed PR #11295 on Reidemeister Schreier algorithm. Remember the blog issue I asked on our gitter channel. Kalevi suggested to be more on the ‘descriptive’ side.

What do we do this week?

Implemented the Reidemeister Schreier algorithm (shortly RS algorithm) and Titze Transformations (shortly TT) in PR #11295 . Most of the pseudo code for RS algorithm is there in the Handbook [1], perhaps majority of the time was spent working with TT. There isn’t any pseudo code available for making that work, but we gathered detailed information from [1] combined with Havas Paper [2].

What issues were there? In the both [1] and [2], there a few assumptions made, like

shall assume that all relators are always cyclically reduced; that is, that whenever a relator is changed, it is immediately replaced by its cyclic reduction.

I opened the issue #11352 regarding a typo I left in coset_enumeration_c. Though I didn’t expect a PR, @kritkaran94 fixed it. Perhaps a good test case which makes use of different value of max_stack_size was suggested by Kalevi. One thing came back to me, “everthing is an object in Python”, the fact that initially CosetTableDefaultMaxLimit was a module level variable initially and we changed it to CosetTable.CosetTableDefaultMaxLimit, module is an object so is a class.

What hasn’t been done?

  • No testing for a few of techniques, for example currently no tests exist for elimination_technique_2, which is a variant of the elimination procedures.

  • TT doesn’t produce the best possible result.

Though doing this seemed easy at first. But I didn’t wanted to apply identity_cyclic_reduction every change as there can be a few instance where it not necessary to do this, perhaps because of the property of words.

The good thing about this week was that I could now understand the limitations that will remain after my GSoC project. The scope of Computational Group Theory is more than what I expected. Apart from that I will be leaving for my college this week stars from 15th of July, perhaps I don’t know how things will shift regarding time for GSoC. Let’s be realistic :)



  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 .</li>

  2. George Havas, “Reidemeister-Schreier program”.