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

Priority:  major  Milestone:  sage7.2 
Component:  coding theory  Keywords:  
Cc:  Johan Rosenkilde  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 7 years ago by
Branch:  → u/dlucas/gs_osullivan 

comment:2 Changed 7 years ago by
Branch:  u/dlucas/gs_osullivan 

Dependencies:  #19666 → #19666, #16896 
Status:  new → needs_review 
comment:3 Changed 7 years ago by
Branch:  → u/dlucas/gs_osullivan 

comment:4 Changed 7 years ago by
Commit:  → b2018d3dd605415d2d64bcb9f7a9346e5c31738d 

Status:  needs_review → 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 7 years ago by
Commit:  b2018d3dd605415d2d64bcb9f7a9346e5c31738d → 143df0da904e57c8a707ad5800e03319238ca370 

comment:6 Changed 7 years ago by
Status:  needs_work → needs_review 

Fixed conflicts, I'm reopening it for review.
comment:7 Changed 7 years ago by
Commit:  143df0da904e57c8a707ad5800e03319238ca370 → e745d8d43d5cc5eb697747418291e93b1827100d 

Branch pushed to git repo; I updated commit sha1. New commits:
e745d8d  Updated to latest beta

comment:8 Changed 7 years ago by
Updated to latest beta, patch now applies properly. It is still open for review.
comment:9 Changed 7 years ago by
Commit:  e745d8d43d5cc5eb697747418291e93b1827100d → 6680fa4f47f0a0019ea3c8d996857c3d44e691ed 

comment:10 Changed 7 years ago by
Milestone:  sage7.0 → sage7.1 

I made some changes, and done a few fixes.
This is still open for review.
comment:11 Changed 7 years ago by
Commit:  6680fa4f47f0a0019ea3c8d996857c3d44e691ed → 8cee9d5a908b4e4608c4641040470c589631c48c 

Branch pushed to git repo; I updated commit sha1. New commits:
8cee9d5  Updated to 7.1beta6

comment:12 Changed 7 years ago by
Branch:  u/dlucas/gs_osullivan → u/jsrn/gs_osullivan 

comment:13 Changed 7 years ago by
Commit:  8cee9d5a908b4e4608c4641040470c589631c48c → 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 7 years ago by
Commit:  8dcba34515b0e471e90a163c258a471702e35032 → 4fe0516b0659ea6e0c458afe4f05bc98cadb3fe7 

Branch pushed to git repo; I updated commit sha1. New commits:
4fe0516  Some documentation typesetting fixes

comment:15 Changed 7 years ago by
Reviewers:  dlucas → 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 7 years ago by
Milestone:  sage7.1 → sage7.2 

Status:  needs_review → 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 7 years ago by
Branch:  u/jsrn/gs_osullivan → 4fe0516b0659ea6e0c458afe4f05bc98cadb3fe7 

Resolution:  → fixed 
Status:  positive_review → 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.