Sage Project Log

In order to help plan better, work in a more structured fashion and have a record of the work we did during the GSoC 2016 in Sage, we maintained a daily project log. This was institutionalised starting with Week 4 and we reproduce the log below.

Week 12:

16th, 17th August:

1. Made all the remaining changes, and pushed the changes to the Gabidulin Ticket. Added the code to the catalog files. There are a couple of issues that need to be resolved based on feedback and then the changes can be made. Commit can be found here.
2. Started writing documentation for the ARMC class. Will push everything I have on that on 18th.
3. Created three new tickets for the stuff left over from the original 13215 ticket and pushed all the relevant code.
4. Started preparing presentation for Sage Days 75. Will share the first draft of outline and ideas on 18th.

15th August:

1. Finished writing documentation and tests for #20970. Finished channel class for the code. After one final pass, will push everything on 16th. There are two tiny issues. One is given a matrix in Sage, how to find a specific non-trivial solution for it. I.e. for matrix A, find non-trivial x_0 s.t. A*x_0 = 0. Currently, the parity evaluation points method is failing because of this. This also causes the channel to fail at times. And the second is suggestions for better names in a couple of places.
2. Created the second ticket from the leftover stuff from #13215. Will push karatsuba and centering tickets on 16th and the last one as well if possible. Otherwise, this will be done by 17th.
3. Updates to the ARMC class. Specifically, adding documentation and tests, and fixing some bugs that were causing incompatibility issues with the Gabidulin Code class.

11th, 12th August:

1. Made changes to 21131. It is open for review.
2. Made changes to finite field ticket. It is open for review. 21088
3. Solved some pickling errors and other comments by Travis. The remaining ones are due to Frobenius it seems. Once it’s decided, whether or not to add experimental decorator, I will update it. Almost open for review.
4. Gabidulin, channel class ready. After one final pass, that ticket will be ready to be done.
5. Prepared Tickets C and D. Will create them and push after one final pass.
6. Weight enumerator and additional methods in ARMC.

9th, 10th August:

1. Created rank_metric.py. Deleted methods according to discussions based on recommended schema. Verified docstrings of inherited methods. Worked on rank support and weight enumerator. Started testing a little. Stuff is not working correctly. Hence the delay in pushing.
2. Gabidulin inherits from this. Removed rank related methods from there. Made that compatible with this.
3. 21088 – finite fields ticket. nearly done. Will push that tomorrow.
4. Made changes to 21131 as per discussion
5. Created Ticket C (karatsuba stuff).

Week 11:

8th August:

1. Further fixes to 13215. (1.5 hrs)
2. Worked on the channel class. But in order to use that in the way David mentioned, I need random element. So I figured it would be better to have a few methods of the ARMC class implemented first. Added new file, inherits from ALC. Basic getter methods, moved matrix to vector and vice versa from Gab. Random element. And Gab inherits from ARMC. (6hrs)
3. Worked on the 21131 ticket. That’s now open for review. (4hrs)

4th August:

1. Wrote channel class for Gabidulin code. Testing continued. Added some checks. Started adding final documentation for every method. (~5hrs)
2. Moved MPE to skew poly. Continued with MVP and interpolation based on comments on trac. (~2.5hrs)

3rd August:

1. Made changes based on comments by Jeroen on Ticket #13215 (~4.5hrs)
2. Fixed Gao Decoder. Edited the construction of Gabidulin Codes to include twist homomorphism. (~3hrs)
3. Made changes to #21131 based on latest comments. (~2hrs)

Week 10:

28th, 29th July:

1. Worked on Ticket #21088. Commits can be found here.
2. Worked on Ticket #21131. Commits can be found here.

27th July:

1. Worked on the comments and discussions on Ticket 13215. (~6hrs)
2. Rewrote and am testing ticket 21088. (~2hrs)

26th July:

1. Fixed documentation build errors from 13215. (~3hrs)
2. Added documentation for interpolation, MSP and MPE. Added documentation for Gao decoder in Gabidulin Codes. (~1.5hrs)
3. Worked on additional polishing of Ticket 13215 based these comments. (~3hrs)

25th July:

1. Resolved single and double backtick inconsistencies from the various files of ticket 13215. Replaced method _cmp_ with _richcmp_ based on recommendations from mentors. removed some latex imports. Commits can be found here. (~3hrs)
2. Worked on adding minimum subspace polynomial, multi-point evaluation and interpolation methods for Ticket 21088. Fixed the various bugs and incompatibility errors. Commit can be found here. (~4hrs)
3. Added documentation and tests for the Gabidulin Code class. Will proceed with the verification of Gao decoder implementation once MPE, MSP and Interpolation are resolved. (~1hr)

Week 9:

20th, 21st, 22nd July:

1. Several threads of discussion regarding the Ticket A were discussed and worked upon. These changes which included removing double imports and unused classes and methods, adding a section in the index file for documentation, improved module description and definition, across various files and finally documentation, tests and code clean up. The commits can be found here.
2. Created ticket B based on past discussions and pushed changes. Added documentation, tests, fixed doctests and removed unused methods. The ticket can be found here.
3. Worked on the Gao Formulation decoder for the Gabidulin Code class.

19th July:

1. Noted down comments from the review of Ticket #13215 and implemented most of the changes. Once the doubts are clarified tomorrow, I’ll submit the edits. (~4hrs)
2. Started working on Ticket B and comparing with its “polynomial” equivalent to identify the problem areas. (~2hrs)

18th July:

1. Fixed final documentation, tests and errors. Cleaned up code and pushed changes. (~5hrs)
2. Edited Gabidulin Codes to adapt to the updated 13215 ticket. Pending: edit minimum subspace polynomial and multi-point evaluation.(~2hrs)
3. Started preparing creation of Ticket B. (~1hr)

Week 8:

16th July:

1. Picked up from the pending work from Friday (yesterday). Added all remaining documentation to the skew_polynomial_element.pyx file. Added all missing tests. (~2.5hrs)
2. Fixed errors in implementation of a couple of methods (is_gen, section). (0.5hrs)
   Phased out side from the _pow_ function. (~1hr)
3. Added small tests and fixes to skew_polynomial_ring_constructor.py. (~1hr) [Only documentation and a couple of tiny methods remain to be added for the Class SkewPolynomialRing_general. Should not take more than an hour or two. Will try and finish this on Sunday. If not, first thing on Monday.]
   

15th July:

1. Went through the skew_polynomial_element.pyx, skew_polynomial_ring.py and skew_polynomial_ring_constructor.py file to identify the remaining tasks so as to reach the “needs review” state. (~2hrs)
2. Added missing methods in skew_polynomial_element.pyx based on discussions. (~2hrs)
3. Added documentation for some private methods. (~1hr)
   

14th July:

1. Cleaned up code, refactored and added some tests and documentation in the skew_polynomial_element.pyx file. (~2hrs)
2. Removed def gcd, xgcd, quo_rem and monic. Renamed lgcd as left_gcd and respectively for all other methods. (~2hrs)
3. Phased out “side” arguments. (~1hr)
4. Solved some bugs that had come up because of the edits and deletions made above. (~1hr)
5. Went through “polynomial_element.pyx” to compare which methods were missing in the skew_polynomial_element.pyx file. Added some. (~2hrs)
   

13th July:

1. Cleaned up, refactored and added some tests and documentation in the skew_polynomial_element.pyx file. (~2hrs)
2. Implemented a special case of the is_unit method for skew polynomials. General case requires support for finding the order of automorphisms. (~1hr)
3. Fixed the final remaining doctests. (~1hr)
4. Finished setting up Sage in Emacs and Sage Notebook. Learning how to use them… (~2hrs)
5. Started phasing out side.py in 13215. (~1hr)
   

12th July:

1. Sorted out cherry pick and pushed changes here. (~1hr)
2. Decided on the most primary cuts to form Ticket A (as per discussions). Pushed changes here. Other files such as side.py are kept for now and will be phased out during refactoring.(~2hrs)
3. Fixed NotImplementedError and other standalone failing doctests from skew_polynomial_element.pyx. See commit here. 127 doctests remain. All of them are caused by some invalid homomorphism problem. Started looking into that. (~3.5hr)
4. Started setting up sage-mode in Emacs and started acquainting myself with it. (~1hr)
   Cleaning up skew_polynomial_element.pyx. (~1 hr)
   

11th July:

1. Prepared notes on the five-way split of the original 13215 ticket and discussed with mentors. (~3hrs)
2. Set up sage notebook. It was giving some error with openssl and required it to be switched off. (~1hr)
3. Using cherry-pick to add commits from public branch test_13215_interactive (not merging properly. it is giving some weird error with the test.sheet file. (~1hr)
   Running doctests on skew_polynomial_element file after the aforementioned commits gives 334 errors. Fixed some very simple basic ones just to see how I can proceed here. (~1hr).
4. Started cutting away portions of 13215_original to form Ticket A. (~2 hrs)
   

10th July:

1. Got an overview of the classes of the ticket and the dependencies between them.
2. Noted down purpose of each. (~2hrs)
3. Wrote down observations about what seems redundant and what needs work in every class. Also made a list of all the classes and methods and functions that have missing docstrings and doctests. (~2.5hrs)
4. Started adding the missing tests and docs for the skew_polynomial_ring.py file. (~1hr)

Week 7:

9th July:

1. Made final edits to the rank-metric conversion and properties. Wrote documentation and tests. Pushed commit here. (~1.5 hr)
2. Removed some of the compile errors from the unencode_nocheck method and supporting methods. Finished writing multi_point_evaluation method. I was using the zero element of Fqm to initialize while I was actually supposed to use the zero element of the message_space (skew polynomial ring). Apart from the main error in #13215, the rest of these methods seem to have no errors. Will confirm once resolved. Pushed commit here (~3 hrs)
3. Made final edits to the documentation and tests of the skew_polynomial_ring_constructor.py file from #13215. Ready to commit. (~1 hr)
   

8th July:

1. Edited gabidulin.py based on comments.
2. Continued writing interpolation of skew_polynomials.

7th July:

1. Fixed one more of the two remaining errors in #13215. It seems that the ‘Left’ object has not been implemented in a lot of places in the skew polynomial ticket.
2. Completed reading relevant sections of the paper mentioned below. Started writing code. Placing it in gabidulin.py for now.
   

6th July:

1. Wrote conversion for matrix form back into vector form. Added support for computing rank-distance, rank-weight.
2. Started reading this for how to interpolate a skew polynomial for the unencode and (future) decode methods.
   

5th July:

1. Fixed the tiny compile errors that were induced in the Skew Poly ticket due to Sage upgrade.
2. Testing of code that was written last Friday and Monday that had gone unchecked. Fixed errors.
3. Wrote conversion into matrix form from vector form of a Gabidulin codeword. Takes a basis as argument.

4th July:

1. Added support for generator matrix, dual code and parity check matrix of Gabidulin Code.
   

Week 6:

1st July:

1. Continued porting to inheritance from SageObject.
   

30th June:

1. Fixed bugs in the evaluation_points, encode, message_space and operator evaluation method for skew polynomials (this bit still needs more work).
2. Based on discussions, removed inheritance of Gabidulin Code class from AbstractLinearCode class. Now moving towards a stand-alone class that inherits from SageObject.
   

29th June:

1. Added support for the default option from below.
2. Created a method for the “ext” function from Lemma 2.1 (of the PhD thesis) on Mapping to Ground Field.
   

28th June:

1. Started adding some tests for the various methods.
2. Added support for an optional argument that can be supplied to the constructor for the code. This allows them to provide a set of linearly independent elements of F_{q^m} over F_q if they choose. Need to add support for default option.
   

27th June:

1. Continued working on constructing a codeword.
2. Trying different input arguments to see which is most convenient to use and still allows flexibility for user.
   

Week 5:

24th June:

1. Evaluated linearized polynomials (sample examples) at various random points.
2. Called relative finite field extension ticket for the vectorial representation of big field in small field in an attempt to form a codeword. This is not working properly. But I think I should have something to present on Monday.

23rd June:

1. Tested construction of linearized polynomials from skew polynomials. By putting in a zero derivation and a Frobenius endomorphism (for a finite field, Frobenius endomorphism is a Frobenius automorphism and hence this is a linearized polynomial ring), it seems to be constructing a ring. Will have to test addition and multiplication once the doctests are solved.
   

22nd June:

1. Submitted Midterm Evaluation. Prepared blog post. Nearly ready to put it up.
2. Read relevant sections of the following papers: Coding with Skew Polynomial Rings, Welch-Berlekamp Like Decoding Algorithm for Gabidulin Codes, Fast Encoding of Gabidulin Codes
   Started designing basic outline of gabidulin.py. Prepared classes for the Code, Encoder and Decoder. I will have a several more details in a design document by tomorrow.

21st June:

1. Continued to fix errors. And pushed recent commits to Ticket 13215. Down to final 2 types of errors.

19th June:

1. Caught a bug. Came down with a flu. Stuck in bed all day.
   

Week 4:

17th June:

1. Continued fixing doctest errors. Relatively slow day, managed to get about 70 solved today. Still about 330 to go. Starting to get the hang of this now. I think.
2. Started drawing up design document for Gabidulin codes. The aim is to try and get all the errors resolved by this weekend and scrub the patch and get it accepted by Monday.

16th June:

1. Continued fixing doctest errors. Managed to get about 200 solved today. Still 400 to go.

15th June:

1. Continued fixing doctest errors in the Skew Polynomial patch. Reported no_attribute_found errors in richcmp, init_cache, and other ValueErrors.
2. Read the Skew Polynomials patch to try and understand what can be used and how for the construction of Gabidulin codes.
   

14th June:

1. Began fixing doctest errors in the Skew Polynomial patch. There were about 650 errors to begin with.
2. Solved some very simple errors such as Deprecation warnings, errors with “interrupt.pxi” etc. About 600 more to go.

13th June:

1. Fixed Cython function declaration compile errors from Skew Polynomials patch.
2. Pushed changes to Ticket #13215
   

12th June:

1. Successfully merged Skew Polynomials patch on local system
2. Fixed deprecated PY_NEW_SAME_TYPE and PY_TYPE_CHECK_EXACT