GSoC 2016 wrap-up

GSoC 2016 Project with SymPy(wrap up): Computational Group Theory Hi, I’m Gaurav Dhingra (@gxyd) and this post is a report of my work for SymPy under Google Summer of Code 2016.

This is also intended to be a description of my work for submission to GSoC’s Final Evaluation.

Work Product Submission

commits in GSoC 2016 product submission: Gaurav Dhingra. GSoC proposal

Pull Requests

#11361 Modified Todd Coxeter algorithm implementation in SymPy

Bugs reported

[closed]

#11449 TypeError on compressing a Coset Table generated by coset table method.

Brief Information

Project: Group Theory

Blog: https://gxyd.github.io/gsoc.html

My Website: https://gxyd.github.io

e-mail: gauravdhingra.gxyd[at]gmail.com, igauravdhingra[at]protonmail.com

I am a pre-final year undergraduate student of Applied Mathematics at IIT Roorkee.

Before GSoC

I heard about the GSoC program and about SymPy org. since of one of my college mate, Prasoon Shukla (he also participated in GSoC with SymPy). I was quite amazed by how mathematics and computer science could intersect and help in solving math problems.

I have been contributing to SymPy from May last year. In the beginning I tended often to work on issues that were more often related to my then on-going courses in my college. In December I completed a basic course on Group Theory, so I thought of choosing to work on Group Theory and I saw quite a few things in CGT were missing from SymPy and those functionalities were already there in GAP and Magma. So I asked them from Kalevi, regarding things that could be taken up for a gsoc project. So finally with some discussions with him and Aaron, I was sure by December end that I was going to work on implementing Finitely Presented Group in SymPy. I looked upto the last GSoC project on CGT by Alexandar Makelov, for reference material that could be used for the implementation and it turned out that the book by Derek Holt, Handbook of Computational Group Theory (will mention as shortly the Handbook).

Though I already started working on PR #10350 for implementation of free groups in beginning January though I started working on the proposal from February beginning.

So what I should do? Since I was quite sure of the project. Well at that moment I thought, since I am a mathematics major, choosing this project would also help me. So I reached out to Kalevi, said to him what I was thinking to do, what could be good for the project. So we worked upon making a good gsoc proposal.

Here is my GSoC proposal. Now that the summer is over and I’ve tackled a lot more with computational group theory, it seems that the main points in my GSoC proposal were:

Implementation of different algebraic structures monoid, free monoid, free group, semi group, free semi group, magma, etc.
Rewriting System for reducing the elements of finitely presented groups.
The Todd-Coxeter algorithm for coset enumeration, used to find the index of a subgroup of a finitely presented group.
Reidemeister Schreier algorithm.
Implementation of main Group class.

Well, I submitted my proposal and needed to wait until April 22 to the result, and then…

I was selected _/_

I got lucky to have Kalevi Suominen like mentor too. Aaron Meurer, the project leader of SymPy was to be co-mentor, and I felt honored to be alloted my preferred mentors.

During GSoC

A more detailed account of my progress can be found on my blog here.

We started working on 7th May, we first started with working on completing the Free Group PR#10350 and we discussed things on our channel sympy/GroupTheory. We had some discussion on whether Basic should be a super-class of FreeGroup or not. In the end we decied not to derive FreeGroup from Basic. Its basic methods had already been written, most of them inspired from GAP software.
For the first point in my proposal (i.e implementation of algebraic structures), we didn’t started with them (infact we never worked on them). We then moved onto the Coset Enumeration which covered 5 weeks of work in my timeline, but we didn’t spend that much time, atleast on the first go at that moment, that did took alomost 3 weeks including the implementation of two strategies of enumeration Felsch and HLT. It was the very heart of our GSoC project. There were quite a few bugs that were there in algorithm, especially the bug #11449, to which the Kalevi found the solution.
For the second point we never reached it, there wasn’t sufficient time for that. Then we decided to rather implement the Low Index Subgroups algortithm. It was quite fun to implement the algorithm, since it gave some good insight into CGT. More on this on blog for week 5.
From here I had passed my mid-term evaluations. Then we started with work on Reidemeister Schreier algorithm. The algorithm was mainly implemeted using the Havas paper, though the current implementation in SymPy doesn’t produce the best simplifed presentation. No good pseudocode is available for the algorithm, the major difficulty being the sequence of applying the operation. More on this on blog for week 6.
After we thought that the result returned by Reidemeister Schreier algorithm we moved onto modified todd coxeter algorithm. The main difficulty in it was defining the $\tau$ which can be read on the our channel for comments by Kalevi, I belive it can help in solving that problem.
As to the fifth point (i.e making Group class), we never worked upon it. Also the topic of Presenation of Finite Groups , could not get much attention, since of my busy college schedule.

Commits/Code written during GSoC

Since I have commited quite a few commits un-related to my project. So I decided to cherry-pick the commits made for my GSoC project. So the combined commits makes the things quite clear. PR for GSoC 2016 product submission: Gaurav Dhingra.

Most annoying issue

issue #11449

After GSoC

There is still much to be done regarding the finitely presented groups. As during the program my efforts were directed mainly towards getting the fundamental algorithms for finitely presented groups in, the overall structure of the module hasn’t received much attention.

The algorithms are in, but the methods in sympy/combinatorics/fp_groups.py are not that much user-friendly. The code organization is not terrible, I think. Some suggestions (both for me and anyone else interested) for future work are:

Cosets in permutation groups: [verbatim-copy of Kalevi’s mail - “next thing to do”] Finding cosets in permutation groups is more challenging to implement since there seems to be no ready-made pseudocode. However, there is a description of the procedure with an example in section 4.6.7. It can be based on the existing implementation of the Screier-Sims algorithm.
Finitely generated abelian groups: [verbatim-copy of Kalevi’s mail - “next thing to do”] There is useful pseudocode in chapter 9 of the book by Holt that should make it fairly easy to implement the basic methods of abelian groups. We should probably try to base the implementation on the code in polys.agca as abelian groups are the same as Z-modules. It is all essentially about linear algebra over the integers.
Complete modified Todd Coxeter algorithm: PR #11361 One bug is currently there in the algorithm, which can be fixed since we have to make assignments to $\tau$. Also currently no tests have been added, which can be added.
Rewriting System: This can be a good candidate for a major work, I included this topic in my proposal though was left untouched. Perhaps GAP could be first seen in this regard. Like always.
Groups folder: After a few of the above mentioned things have been done, I believe it could be a good time to make a folder named groups, since finitely presented groups should not be a part of combinatorics module which would contain the all algebraic structures including the permutation groups.
Non-associative algebra: (Perhaps I got the spelling of associative this time right!) Albert CAS could be used to understand the workings related to non-associative algebra, it contains quite good functionalities.

Things I did right/wrong

I often lagged in writing blogs.
I worked more than expected hours before 15 July (before college started) but much less in the last one month of GSoC because of a little busy schedule.

Conclusion

I had say that I did about 70% of the work I promised to do in my proposal, considering that I also did two non-included task of Low Index subgroups algorithm and Modified Todd Coxeter algorithm, so I can say I swapped my work. It is good enough, and I hope to get back to extending the things that I have started. There’s still some revision to be made, some code to be clean up. And I’m doing that.

I don’t really know if I’ll pass final evaluations by Google, but, regardless, I’m really glad for all the coding and development experience I got during these weeks. I’ll probably use for personal projects, may be in Dissertation in last year, and try to contribute more to SymPy.

I appreciate the help of my mentor Kalevi Suominen who was always there for any query that I had regarding Group Theory in project, and I appreciate his ability to reply back within 1 hour for any message I left any time of day and every day of the week including weekend (I call it 1-hour rule). I think he was a wonderful mentor and I learnt a lot from him, and my co-mentor Aaron Meurer, the current project leader of SymPy, and the entire SymPy community for helping me out and reviewing my work!

Also thank you Google.

अलविदा !

Find me on Github and Twitter