Opened 7 years ago

Closed 7 years ago

#19722 closed enhancement (fixed)

Lee O'Sullivan interpolation algorithm for Guruswami-Sudan decoder

Reported by: David Lucas Owned by:
Priority: major Milestone: sage-7.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:

Status badges

Description

This ticket introduces a new, faster algorithm for the interpolation step of the Guruswami-Sudan 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 David Lucas

Branch: u/dlucas/gs_osullivan

comment:2 Changed 7 years ago by David Lucas

Branch: u/dlucas/gs_osullivan
Dependencies: #19666#19666, #16896
Status: newneeds_review

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.

Last edited 7 years ago by David Lucas (previous) (diff)

comment:3 Changed 7 years ago by David Lucas

Branch: u/dlucas/gs_osullivan

comment:4 Changed 7 years ago by David Lucas

Commit: b2018d3dd605415d2d64bcb9f7a9346e5c31738d
Status: needs_reviewneeds_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:

853d77cInitial copy of LV and LP methods from codinglib
dc14effWIP
323e675Fix return type when input type is a polynomial matrix
12b7239Drop dedent since it didn't have the intended purpose
bf1732dFixed the base ring fix when input is over polynomial ring.
67c5636Ok, last fix
856282aMerge branch 't/16896/rework_of_row_reduced_form_weak_popov_form_calling_convention' into gs_osullivan
f7ddf14Methods related Lee-O'Sullivan algorithm completely documented and cleaned
3189849Rewrote documentation for new methods in utils.py
b2018d3New option to select Lee O'Sullivan algorithm at construction time in the decoder

comment:5 Changed 7 years ago by git

Commit: b2018d3dd605415d2d64bcb9f7a9346e5c31738d143df0da904e57c8a707ad5800e03319238ca370

Branch pushed to git repo; I updated commit sha1. New commits:

c17ffe9Updated to latest beta and fixed conflicts
143df0dFixed bug in utils.py documentation

comment:6 Changed 7 years ago by David Lucas

Status: needs_workneeds_review

Fixed conflicts, I'm reopening it for review.

comment:7 Changed 7 years ago by git

Commit: 143df0da904e57c8a707ad5800e03319238ca370e745d8d43d5cc5eb697747418291e93b1827100d

Branch pushed to git repo; I updated commit sha1. New commits:

e745d8dUpdated to latest beta

comment:8 Changed 7 years ago by David Lucas

Updated to latest beta, patch now applies properly. It is still open for review.

comment:9 Changed 7 years ago by git

Commit: e745d8d43d5cc5eb697747418291e93b1827100d6680fa4f47f0a0019ea3c8d996857c3d44e691ed

Branch pushed to git repo; I updated commit sha1. New commits:

7b94232Updated to 7.1beta5 and fixed conflicts
3991f16Added an extra doctest for the decoder class and fixed a bug
c0b4f4bReworked documentation in utils.py
6680fa4Renamed input for Lee-O'Sullivan methods

comment:10 Changed 7 years ago by David Lucas

Milestone: sage-7.0sage-7.1

I made some changes, and done a few fixes.

This is still open for review.

comment:11 Changed 7 years ago by git

Commit: 6680fa4f47f0a0019ea3c8d996857c3d44e691ed8cee9d5a908b4e4608c4641040470c589631c48c

Branch pushed to git repo; I updated commit sha1. New commits:

8cee9d5Updated to 7.1beta6

comment:12 Changed 7 years ago by Johan Rosenkilde

Branch: u/dlucas/gs_osullivanu/jsrn/gs_osullivan

comment:13 Changed 7 years ago by Johan Rosenkilde

Commit: 8cee9d5a908b4e4608c4641040470c589631c48c8dcba34515b0e471e90a163c258a471702e35032

Hi, I've looked through the code and it looks good. I made a number of minor modifications directly. The most major are:

  1. Rename "weight" to "shift". This is the standard nomenclature in computer algebra.
  2. 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 re-test and re-check documentation after that.


New commits:

32ef5eaMerge branch 'u/dlucas/gs_osullivan' of git://trac.sagemath.org/sage into 19722_gs_lee_osullivan
7e81121rename weight to shift (more standard nomenclature)
99a7c1fRemove support for fractional weights
94366aaElaborated on doc for `lee_osullivan_module`.
3669451Improved some namings and a bit of doc
8dcba34Remove tau parameter from lee_osullivan_module

comment:14 Changed 7 years ago by git

Commit: 8dcba34515b0e471e90a163c258a471702e350324fe0516b0659ea6e0c458afe4f05bc98cadb3fe7

Branch pushed to git repo; I updated commit sha1. New commits:

4fe0516Some documentation typesetting fixes

comment:15 Changed 7 years ago by Johan Rosenkilde

Reviewers: dlucasDavid 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 David Lucas

Milestone: sage-7.1sage-7.2
Status: needs_reviewpositive_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 Volker Braun

Branch: u/jsrn/gs_osullivan4fe0516b0659ea6e0c458afe4f05bc98cadb3fe7
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.