#21333 closed enhancement (fixed)
Port Alekhnovich algorithm from CodingLib
Reported by:  bruno  Owned by:  

Priority:  major  Milestone:  sage8.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 )
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 3 years ago by
 Dependencies set to 21331
comment:2 Changed 3 years ago by
 Dependencies changed from 21331 to #21331
comment:3 Changed 3 years ago by
 Branch set to u/bruno/port_alekhnovich_algorithm_from_codinglib
comment:4 Changed 3 years ago by
 Commit set to 9b6bae34a6b1c4b55bad69ea7a058221207cafdc
 Status changed from new to needs_review
comment:5 Changed 3 years ago by
 Commit changed from 9b6bae34a6b1c4b55bad69ea7a058221207cafdc to 2dd574615d6ceaef0adb3c5d8a3b277b490d08b3
Branch pushed to git repo; I updated commit sha1. New commits:
2dd5746  21333: Improve docstrings

comment:6 Changed 3 years ago by
 Description modified (diff)
comment:7 Changed 3 years ago by
 Keywords rd3 added
 Reviewers set to Johan Rosenkilde
 Status changed from needs_review to positive_review
I made microscopic lastminute fixes. Positive review.
comment:8 Changed 3 years ago by
 Branch changed from u/bruno/port_alekhnovich_algorithm_from_codinglib to u/jsrn/port_alekhnovich_algorithm_from_codinglib
comment:9 Changed 3 years ago by
 Commit changed from 2dd574615d6ceaef0adb3c5d8a3b277b490d08b3 to 1f773c3c3824af00dee03fa2d34dcf198675350d
 Milestone changed from sage7.4 to sage7.7
comment:10 Changed 3 years ago by
 Branch changed from u/jsrn/port_alekhnovich_algorithm_from_codinglib to 1f773c3c3824af00dee03fa2d34dcf198675350d
 Resolution set to fixed
 Status changed from positive_review to closed
Note: See
TracTickets for help on using
tickets.
I decided to make Alekhnovich algorithm default (both for "simply" rootfinding in for polynomials, and as rootfinder 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:
Basic infrastructure
Add ROth Ruckenstein algorithm
Remove RothRuckenstein alg from coding
Refine default degree bound
Remove rootfinding from doc
Use polys instead of lists in rothruckenstein
Doctest roth_ruckenstein_root_finder
21333: Add Aleknovich algorithm and make it default since faster
21333: Make Alekhnovich algorithm available and default for GuruswamiSudan list decoding