Opened 2 years ago

Closed 2 years ago

#21331 closed enhancement (fixed)

Make Roth-Ruckenstein algorithm a method of polynomials

Reported by: bruno Owned by:
Priority: major Milestone: sage-7.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 Roth-Ruckenstein 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 2 years ago by bruno

  • Branch set to u/bruno/y-root_finding

comment:2 Changed 2 years ago by bruno

  • Commit set to e19ef2a3a04ccabe1256482256a333ec5826ab71

There remains one step to perform: Remove Roth-Ruckenstein from coding and branch the new implementation.


New commits:

ced566cBasic infrastructure
e19ef2aAdd ROth Ruckenstein algorithm

comment:3 Changed 2 years ago by git

  • Commit changed from e19ef2a3a04ccabe1256482256a333ec5826ab71 to 4c85e838e07f4aad59b09bcf590ea723d92a10c3

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

60972c5Remove Roth-Ruckenstein alg from coding
4c85e83Refine default degree bound

comment:4 Changed 2 years ago by bruno

  • Cc dlucas added
  • Status changed from new to needs_review

comment:5 follow-up: Changed 2 years ago by 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%

Last edited 2 years ago by chapoton (previous) (diff)

comment:6 in reply to: ↑ 5 Changed 2 years ago by bruno

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

  • Commit changed from 4c85e838e07f4aad59b09bcf590ea723d92a10c3 to 458ffc2e0c03b03c24e3c38806f27bc0f52a5c68

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

3323e3bRemove rootfinding from doc
458ffc2Use polys instead of lists in roth-ruckenstein

comment:8 Changed 2 years ago by git

  • Commit changed from 458ffc2e0c03b03c24e3c38806f27bc0f52a5c68 to 01378dcfdc19033ae5a6d755e75b315176e0656d

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

01378dcDoctest roth_ruckenstein_root_finder

comment:9 Changed 2 years ago by bruno

  • Status changed from needs_work to needs_review

comment:10 Changed 2 years ago by turkuozlum

  • 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 Roth-Ruckenstein. It seems OK.

comment:11 Changed 2 years ago by vbraun

  • Branch changed from u/bruno/y-root_finding to 01378dcfdc19033ae5a6d755e75b315176e0656d
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.