Opened 3 years ago
Closed 3 years ago
#21331 closed enhancement (fixed)
Make RothRuckenstein algorithm a method of polynomials
Reported by:  bruno  Owned by:  

Priority:  major  Milestone:  sage7.4 
Component:  commutative algebra  Keywords:  sd75, polynomial, root finding 
Cc:  jsrn, dlucas  Merged in:  
Authors:  Bruno Grenet  Reviewers:  Turku Ozlum Celik 
Report Upstream:  N/A  Work issues:  
Branch:  01378dc (Commits)  Commit:  01378dcfdc19033ae5a6d755e75b315176e0656d 
Dependencies:  Stopgaps: 
Description
The coding part of Sage (see #18846) contains RothRuckenstein algorithm to compute the roots of a polynomial Q(y)
with coefficients in F[x]
(where F
is a finite field). The purpose of this ticket is to move the implementation to make this algorithm a method of polynomials.
Toward this end, we also define a generic implementation for roots of univariate polynomials over univariate polynomial rings, that goes through their factorization. And this requires to implement the factorization for these "recursive" polynomial rings: Currently, the algorithm consists in flattening the recursive polynomial ring and use methods for multivariate polynomial rings.
Change History (11)
comment:1 Changed 3 years ago by
 Branch set to u/bruno/yroot_finding
comment:2 Changed 3 years ago by
 Commit set to e19ef2a3a04ccabe1256482256a333ec5826ab71
comment:3 Changed 3 years ago by
 Commit changed from e19ef2a3a04ccabe1256482256a333ec5826ab71 to 4c85e838e07f4aad59b09bcf590ea723d92a10c3
comment:4 Changed 3 years ago by
 Cc dlucas added
 Status changed from new to needs_review
comment:5 followup: ↓ 6 Changed 3 years ago by
doc, does not build, see patchbot report:
+[dochtml] Warning: Could not import sage.coding.guruswami_sudan.rootfinding No module named rootfinding
comment:6 in reply to: ↑ 5 Changed 3 years ago by
 Status changed from needs_review to needs_work
Replying to chapoton:
doc, does not build, see patchbot report:
+[dochtml] Warning: Could not import sage.coding.guruswami_sudan.rootfinding No module named rootfinding
and incomplete coverage: +Decreased doctests in coding/guruswami_sudan/gs_decoder.py: from 17 / 17 = 100% to 17 / 18 = 94%
Argh, I did not check to documentation well enough! I'm working on it.
comment:7 Changed 3 years ago by
 Commit changed from 4c85e838e07f4aad59b09bcf590ea723d92a10c3 to 458ffc2e0c03b03c24e3c38806f27bc0f52a5c68
comment:8 Changed 3 years ago by
 Commit changed from 458ffc2e0c03b03c24e3c38806f27bc0f52a5c68 to 01378dcfdc19033ae5a6d755e75b315176e0656d
Branch pushed to git repo; I updated commit sha1. New commits:
01378dc  Doctest roth_ruckenstein_root_finder

comment:9 Changed 3 years ago by
 Status changed from needs_work to needs_review
comment:10 Changed 3 years ago by
 Reviewers set to Turku Ozlum Celik
 Status changed from needs_review to positive_review
I checked the ticket by following the checklist and the algorithm by considering the paper of RothRuckenstein. It seems OK.
comment:11 Changed 3 years ago by
 Branch changed from u/bruno/yroot_finding to 01378dcfdc19033ae5a6d755e75b315176e0656d
 Resolution set to fixed
 Status changed from positive_review to closed
There remains one step to perform: Remove RothRuckenstein from
coding
and branch the new implementation.New commits:
Basic infrastructure
Add ROth Ruckenstein algorithm