Opened 6 years ago
Closed 6 years ago
#19722 closed enhancement (fixed)
Lee O'Sullivan interpolation algorithm for GuruswamiSudan decoder
Reported by:  dlucas  Owned by:  

Priority:  major  Milestone:  sage7.2 
Component:  coding theory  Keywords:  
Cc:  jsrn  Merged in:  
Authors:  Johan Sebastian Rosenkilde Nielsen, David Lucas  Reviewers:  David Lucas, Johan Sebastian Rosenkilde Nielsen 
Report Upstream:  N/A  Work issues:  
Branch:  4fe0516 (Commits, GitHub, GitLab)  Commit:  4fe0516b0659ea6e0c458afe4f05bc98cadb3fe7 
Dependencies:  #19666, #16896  Stopgaps: 
Description
This ticket introduces a new, faster algorithm for the interpolation step of the GuruswamiSudan list decoder proposed in #19666, called Lee O'Sullivan algorithm.
The code proposed here relies extensively on the code written by Johan Nielsen in codinglib. He wrote all the algorithms and mathematical content.
Change History (17)
comment:1 Changed 6 years ago by
 Branch set to u/dlucas/gs_osullivan
comment:2 Changed 6 years ago by
 Branch u/dlucas/gs_osullivan deleted
 Dependencies changed from #19666 to #19666, #16896
 Status changed from new to needs_review
comment:3 Changed 6 years ago by
 Branch set to u/dlucas/gs_osullivan
comment:4 Changed 6 years ago by
 Commit set to b2018d3dd605415d2d64bcb9f7a9346e5c31738d
 Status changed from needs_review to needs_work
I pushed my branch again which it's been deleted, but now there is some conflict with the latest beta. I change this ticket to needs work until I fix this.
Last 10 new commits:
853d77c  Initial copy of LV and LP methods from codinglib

dc14eff  WIP

323e675  Fix return type when input type is a polynomial matrix

12b7239  Drop dedent since it didn't have the intended purpose

bf1732d  Fixed the base ring fix when input is over polynomial ring.

67c5636  Ok, last fix

856282a  Merge branch 't/16896/rework_of_row_reduced_form_weak_popov_form_calling_convention' into gs_osullivan

f7ddf14  Methods related LeeO'Sullivan algorithm completely documented and cleaned

3189849  Rewrote documentation for new methods in utils.py

b2018d3  New option to select Lee O'Sullivan algorithm at construction time in the decoder

comment:5 Changed 6 years ago by
 Commit changed from b2018d3dd605415d2d64bcb9f7a9346e5c31738d to 143df0da904e57c8a707ad5800e03319238ca370
comment:6 Changed 6 years ago by
 Status changed from needs_work to needs_review
Fixed conflicts, I'm reopening it for review.
comment:7 Changed 6 years ago by
 Commit changed from 143df0da904e57c8a707ad5800e03319238ca370 to e745d8d43d5cc5eb697747418291e93b1827100d
Branch pushed to git repo; I updated commit sha1. New commits:
e745d8d  Updated to latest beta

comment:8 Changed 6 years ago by
Updated to latest beta, patch now applies properly. It is still open for review.
comment:9 Changed 6 years ago by
 Commit changed from e745d8d43d5cc5eb697747418291e93b1827100d to 6680fa4f47f0a0019ea3c8d996857c3d44e691ed
comment:10 Changed 6 years ago by
 Milestone changed from sage7.0 to sage7.1
I made some changes, and done a few fixes.
This is still open for review.
comment:11 Changed 6 years ago by
 Commit changed from 6680fa4f47f0a0019ea3c8d996857c3d44e691ed to 8cee9d5a908b4e4608c4641040470c589631c48c
Branch pushed to git repo; I updated commit sha1. New commits:
8cee9d5  Updated to 7.1beta6

comment:12 Changed 6 years ago by
 Branch changed from u/dlucas/gs_osullivan to u/jsrn/gs_osullivan
comment:13 Changed 6 years ago by
 Commit changed from 8cee9d5a908b4e4608c4641040470c589631c48c to 8dcba34515b0e471e90a163c258a471702e35032
Hi, I've looked through the code and it looks good. I made a number of minor modifications directly. The most major are:
 Rename "weight" to "shift". This is the standard nomenclature in computer algebra.
 Remove support for fractional shifts in the helper methods of
utils.py
. This is not needed for Lee and O'Sullivan, and it simplifies those helpers a lot.
Apart from that, I just simplified a few things, renamed some things and reformulated some docs. I also elaborated some doc strings here and there, where I found that further details might be nice for the user.
I'm currently recompiling after make distclean
and I will retest and recheck documentation after that.
New commits:
32ef5ea  Merge branch 'u/dlucas/gs_osullivan' of git://trac.sagemath.org/sage into 19722_gs_lee_osullivan

7e81121  rename weight to shift (more standard nomenclature)

99a7c1f  Remove support for fractional weights

94366aa  Elaborated on doc for `lee_osullivan_module`.

3669451  Improved some namings and a bit of doc

8dcba34  Remove tau parameter from lee_osullivan_module

comment:14 Changed 6 years ago by
 Commit changed from 8dcba34515b0e471e90a163c258a471702e35032 to 4fe0516b0659ea6e0c458afe4f05bc98cadb3fe7
Branch pushed to git repo; I updated commit sha1. New commits:
4fe0516  Some documentation typesetting fixes

comment:15 Changed 6 years ago by
 Reviewers changed from dlucas to David Lucas, Johan Sebastian Rosenkilde Nielsen
Fixed some last things wrt. documentation. All tests in sage/coding
and all src/doc
pass, and I'm testing the rest of the library now.
If you can agree to my changes, feel free to set the ticket to "positive review".
comment:16 Changed 6 years ago by
 Milestone changed from sage7.1 to sage7.2
 Status changed from needs_review to positive_review
Hello,
Thanks for the changes! I ran the tests on my side, everything passes, online documentation is fine, and I agree with your changes.
Setting this ticket to positive_review
.
comment:17 Changed 6 years ago by
 Branch changed from u/jsrn/gs_osullivan to 4fe0516b0659ea6e0c458afe4f05bc98cadb3fe7
 Resolution set to fixed
 Status changed from positive_review to closed
I pushed the patch, this ticket is now open for review. I modified the description because it also relies on #16896
Same thing that in #19666, I added myself as a reviewer because I read Johan's code while porting it, but I of course need someone to review my documentation and tests.