GSoC Week 12
Hi all, here’s a brief summary of the 12th week of my GSoC:
Last week I uploaded the test-coverage files on my website, that revealed some interesting places where a few versions of scan routine in coset enumeration have un-tested if-elif-else case.
As we are now approaching the end of GSoC time period, we decided to do some testing with some of the examples from 1973cdhw paper [2]. Coset Enumeration got my attention again since:
There seemed to be one bug raising TypeError so opened issue sympy/sympy/#11449, resulting from coset enumeration by the coset-table based method. From beginning it was clear that the issue was not in compress() method. It was quite difficult for me get onto the main source of problem. But then Kalevi had a closer look on the pseudo-code in Derek Holt and also in Sims Finitely Presented Groups.
I wrote docstrings for a few of methods and fixed the issue #11449 in PR #11460.
The problem there in code is explained briefly below
Previous code-snippet
1 i = 0
2 while i < len(C.omega):
3 alpha = C.omega[i]
4 i += 1
5 for x in C.A:
6 if C.table[alpha][C.A_dict[x]] is None:
7 C.define_f(alpha, x)
8 C.process_deductions(R_c_list[C.A_dict[x]], R_c_list[C.A_dict_inv[x]])
After code-snippet
1 while alpha < len(C.table):
2 if C.p[alpha] == alpha:
3 for x in C.A:
4 if C.p[alpha] != alpha:
5 break
6 if C.table[alpha][C.A_dict[x]] is None:
7 C.define_c(alpha, x)
8 C.process_deductions(R_c_list[C.A_dict[x]], R_c_list[C.A_dict_inv[x]])
Here $\alpha$ looks over in till $\lt$ C.table. This way all elements of $C.\Omega$ are tested even in case that the set becomes very small. The inner for $x$ loop should also tests $p[i]$ at each round and break if that becomes different from $i$.
The changes that have been addressed in PR #11460 also include chaging the file name free_group.py to free_groups.py, similar to what we have.
It seems that Presentation of Permutation Groups won’t happen during GSoC since there’s just one more week; instead, I plan to focus on improving and completing the current PR’s #11361 on Modified Todd-Coxeter algorithm and PR #11460 on addition of docstrings and better user methods.
One more thing, that I would start in this week though may not be completed this week will be the sphinx documentation of finitely presented groups. I found the documentation of Poly’s module by Kalevi very much readable and interesting, may be I can seek to follow that.
References
-
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 .