Opened 3 years ago

Closed 3 years ago

#29652 closed enhancement (fixed)

Implement polynomial subresultants

Reported by: Miguel Marco Owned by:
Priority: major Milestone: sage-9.2
Component: algebra Keywords: subresultants
Cc: Sebastian Oehms, Travis Scrimshaw Merged in:
Authors: Miguel Marco Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: ddc80b7 (Commits, GitHub, GitLab) Commit: ddc80b725b6de595b5d804938ad44da123ebfa5f
Dependencies: Stopgaps:

Status badges

Description

This ticket implements the computation of the nonzero polynomial subresultants, following [1]

[1] http://www-math.univ-poitiers.fr/~ducos/Travaux/sous-resultants.pdf

Change History (15)

comment:1 Changed 3 years ago by Miguel Marco

Branch: u/mmarco/subresultants

comment:2 Changed 3 years ago by Miguel Marco

Commit: c27afce1c8810948f1f8804c1d0e164b14a96045
Status: newneeds_review

New commits:

fd52240First implementation of subresultants
c27afceCover multivariate case

comment:3 Changed 3 years ago by Travis Scrimshaw

Milestone: sage-9.1sage-9.2
Reviewers: Travis Scrimshaw
Type: PLEASE CHANGEenhancement

Minor points for PEP8:

-delta = d-e
+delta = d - e
-                            a = a/2
-                            c = c**2/y
+                            a /= 2
+                            c = c**2 / y
                             if n >= a:
-                                c = c*x/y
+                                c = c * x / y
                                 n = n - a
-                        C = c*S[0]/y
                 else:
-                    C = B.leading_coefficient()**(delta-1) * B / s**(delta-1)
                 S = [ring(C)] + S
             else:
                 C = B
             if e == 0:
                 return S
-            B = A.pseudo_quo_rem(-B)[1]/(s**delta*A.leading_coefficient())
+            B = A.pseudo_quo_rem(-B)[1] / (s**delta * A.leading_coefficient())

Also could you remove a few of the blanklines after the subresultants before composed_op just to make it a bit more standardized?

Once these are done/ignored, you can set a positive review.

comment:4 Changed 3 years ago by git

Commit: c27afce1c8810948f1f8804c1d0e164b14a960451b969d68ee22ecbcc12713f02636b5aa692e5b40

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

1b969d6PEP 8 corrections

comment:5 Changed 3 years ago by Miguel Marco

Status: needs_reviewpositive_review

Thanks for the review!

comment:6 Changed 3 years ago by François Bissey

Documentation doesn't build because of an indentation error.

OSError: /dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python3_7/build/lib/sage/rings/polynomial/multi_polynomial_element.py:docstring of sage.rings.polynomial.multi_polynomial_element.MPolynomial_polydict.subresultants:14: WARNING: Unexpected indentation.

Which I think means there is one leading space too many on this line

             -x^3 - x^2*y + 6*x^2 + 5*x*y - 11*x - 6*y + 6]

and most likely in other continued lines in various docstrings of this ticket.

comment:7 Changed 3 years ago by François Bissey

Status: positive_reviewneeds_work

comment:8 in reply to:  6 Changed 3 years ago by Travis Scrimshaw

Replying to fbissey:

Documentation doesn't build because of an indentation error.

OSError: /dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python3_7/build/lib/sage/rings/polynomial/multi_polynomial_element.py:docstring of sage.rings.polynomial.multi_polynomial_element.MPolynomial_polydict.subresultants:14: WARNING: Unexpected indentation.

Which I think means there is one leading space too many on this line

             -x^3 - x^2*y + 6*x^2 + 5*x*y - 11*x - 6*y + 6]

and most likely in other continued lines in various docstrings of this ticket.

No, that isn't the problem (this is done in many places in Sage, plus I like the space to differentiate it from other output and to match what Sage does). Actually it comes from:

multi_polynomial_element.subresultants

missing an EXAMPLES::.

Also, one other trivial change in 2 files:

-subresultants(self, other, variable= None):
+subresultants(self, other, variable=None):

comment:9 Changed 3 years ago by François Bissey

I thought it was curious. Your explanation makes much more sense, I obviously don't write enough sage documentation.

comment:10 in reply to:  9 Changed 3 years ago by Travis Scrimshaw

Replying to fbissey:

I thought it was curious. Your explanation makes much more sense, I obviously don't write enough sage documentation.

You do quite a lot of more important things for Sage. ;P

comment:11 Changed 3 years ago by git

Commit: 1b969d68ee22ecbcc12713f02636b5aa692e5b40530737a5fc4c9eacffb917da1299fb8ebf4ad534

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

530737aAdded examples and fixed minor style

comment:12 Changed 3 years ago by git

Commit: 530737a5fc4c9eacffb917da1299fb8ebf4ad534ddc80b725b6de595b5d804938ad44da123ebfa5f

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

ddc80b7Fixed coefficient signs in doctest

comment:13 Changed 3 years ago by Miguel Marco

Status: needs_workneeds_review

Thanks for catching that up.

comment:14 Changed 3 years ago by Travis Scrimshaw

Status: needs_reviewpositive_review

Thank you both.

comment:15 Changed 3 years ago by Volker Braun

Branch: u/mmarco/subresultantsddc80b725b6de595b5d804938ad44da123ebfa5f
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.