Opened 6 years ago

Closed 5 years ago

#19722 closed enhancement (fixed)

Lee O'Sullivan interpolation algorithm for Guruswami-Sudan decoder

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

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 6 years ago by dlucas

  • Branch set to u/dlucas/gs_osullivan

comment:2 Changed 6 years ago by dlucas

  • Branch u/dlucas/gs_osullivan deleted
  • Dependencies changed from #19666 to #19666, #16896
  • Status changed from new to needs_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 6 years ago by dlucas (previous) (diff)

comment:3 Changed 6 years ago by dlucas

  • Branch set to u/dlucas/gs_osullivan

comment:4 Changed 6 years ago by dlucas

  • 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:

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 6 years ago by git

  • Commit changed from b2018d3dd605415d2d64bcb9f7a9346e5c31738d to 143df0da904e57c8a707ad5800e03319238ca370

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 6 years ago by dlucas

  • Status changed from needs_work to needs_review

Fixed conflicts, I'm reopening it for review.

comment:7 Changed 6 years ago by git

  • Commit changed from 143df0da904e57c8a707ad5800e03319238ca370 to e745d8d43d5cc5eb697747418291e93b1827100d

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

e745d8dUpdated to latest beta

comment:8 Changed 6 years ago by dlucas

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

comment:9 Changed 6 years ago by git

  • Commit changed from e745d8d43d5cc5eb697747418291e93b1827100d to 6680fa4f47f0a0019ea3c8d996857c3d44e691ed

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 6 years ago by dlucas

  • Milestone changed from sage-7.0 to sage-7.1

I made some changes, and done a few fixes.

This is still open for review.

comment:11 Changed 6 years ago by git

  • Commit changed from 6680fa4f47f0a0019ea3c8d996857c3d44e691ed to 8cee9d5a908b4e4608c4641040470c589631c48c

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

8cee9d5Updated to 7.1beta6

comment:12 Changed 5 years ago by jsrn

  • Branch changed from u/dlucas/gs_osullivan to u/jsrn/gs_osullivan

comment:13 Changed 5 years ago by jsrn

  • 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:

  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 5 years ago by git

  • Commit changed from 8dcba34515b0e471e90a163c258a471702e35032 to 4fe0516b0659ea6e0c458afe4f05bc98cadb3fe7

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

4fe0516Some documentation typesetting fixes

comment:15 Changed 5 years ago by jsrn

  • 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 5 years ago by dlucas

  • Milestone changed from sage-7.1 to sage-7.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 5 years ago by vbraun

  • Branch changed from u/jsrn/gs_osullivan to 4fe0516b0659ea6e0c458afe4f05bc98cadb3fe7
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.