Opened 2 years ago

Closed 21 months ago

Last modified 21 months ago

#21333 closed enhancement (fixed)

Port Alekhnovich algorithm from CodingLib

Reported by: bruno Owned by:
Priority: major Milestone: sage-8.0
Component: commutative algebra Keywords: sd75, polynomial, root finding, rd3
Cc: jsrn, dlucas Merged in:
Authors: Bruno Grenet Reviewers: Johan Rosenkilde
Report Upstream: N/A Work issues:
Branch: 1f773c3 (Commits) Commit: 1f773c3c3824af00dee03fa2d34dcf198675350d
Dependencies: #21331 Stopgaps:

Description (last modified by bruno)

Johan Rosenkilde's Codinglib implements Alekhnovich algorithm to compute the roots (in F[x]) of a polynomial in F[x][y], where F is a finite field.

This ticket ports this implementation to Sage. The proposed implementation is a modification of Codinglib's code, using Sage's polynomials instead of (explicitly manipulated) list of coefficients. As a result, we get a slight improvement on the running times. (Quick and dirty tests show gain of 10% to 20%.)

Change History (11)

comment:1 Changed 2 years ago by bruno

  • Dependencies set to 21331

comment:2 Changed 2 years ago by bruno

  • Dependencies changed from 21331 to #21331

comment:3 Changed 2 years ago by bruno

  • Branch set to u/bruno/port_alekhnovich_algorithm_from_codinglib

comment:4 Changed 2 years ago by bruno

  • Commit set to 9b6bae34a6b1c4b55bad69ea7a058221207cafdc
  • Status changed from new to needs_review

I decided to make Alekhnovich algorithm default (both for "simply" root-finding in for polynomials, and as root-finder for GuruswamiSudan decoder). Tell me if you view it as a bad idea!

Note: First 7 commits are from #21331. Only two latest commits (tagged 21333) really belong to this ticket.


New commits:

ced566cBasic infrastructure
e19ef2aAdd ROth Ruckenstein algorithm
60972c5Remove Roth-Ruckenstein alg from coding
4c85e83Refine default degree bound
3323e3bRemove rootfinding from doc
458ffc2Use polys instead of lists in roth-ruckenstein
01378dcDoctest roth_ruckenstein_root_finder
1fa0e0e21333: Add Aleknovich algorithm and make it default since faster
9b6bae321333: Make Alekhnovich algorithm available and default for Guruswami-Sudan list decoding
Last edited 2 years ago by bruno (previous) (diff)

comment:5 Changed 2 years ago by git

  • Commit changed from 9b6bae34a6b1c4b55bad69ea7a058221207cafdc to 2dd574615d6ceaef0adb3c5d8a3b277b490d08b3

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

2dd574621333: Improve docstrings

comment:6 Changed 2 years ago by bruno

  • Description modified (diff)

comment:7 Changed 22 months ago by jsrn

  • Keywords rd3 added
  • Reviewers set to Johan Rosenkilde
  • Status changed from needs_review to positive_review

I made microscopic last-minute fixes. Positive review.

comment:8 Changed 22 months ago by jsrn

  • Branch changed from u/bruno/port_alekhnovich_algorithm_from_codinglib to u/jsrn/port_alekhnovich_algorithm_from_codinglib

comment:9 Changed 22 months ago by vbraun

  • Commit changed from 2dd574615d6ceaef0adb3c5d8a3b277b490d08b3 to 1f773c3c3824af00dee03fa2d34dcf198675350d
  • Milestone changed from sage-7.4 to sage-7.7

New commits:

8c7442dMerge branch 'u/bruno/port_alekhnovich_algorithm_from_codinglib' of trac.sagemath.org:sage into 21333_alekhnovich
1f773c3Authors and very small fixes

comment:10 Changed 21 months ago by vbraun

  • Branch changed from u/jsrn/port_alekhnovich_algorithm_from_codinglib to 1f773c3c3824af00dee03fa2d34dcf198675350d
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:11 Changed 21 months ago by jdemeyer

  • Milestone changed from sage-7.7 to sage-8.0

Milestone renamed

Note: See TracTickets for help on using tickets.