Opened 6 years ago
Closed 5 years ago
#15061 closed defect (fixed)
PARI and Singular can't handle all polynomial resultants
Reported by:  robharron  Owned by:  

Priority:  major  Milestone:  sage6.3 
Component:  algebra  Keywords:  pari, resultant, sylvester matrix 
Cc:  Merged in:  
Authors:  Robert Harron, Peter Bruin  Reviewers:  Martin von Gagern 
Report Upstream:  N/A  Work issues:  
Branch:  51523b1 (Commits)  Commit:  51523b10dd11ba8e7b0689b351130e7596decc23 
Dependencies:  Stopgaps: 
Description
Consider the following:
sage: R.<T> = PowerSeriesRing(QQ) sage: F = R([1,1],2) sage: F 1 + T + O(T^2) sage: RP.<x> = PolynomialRing(R) sage: P = x^2  F sage: P.resultant(P.derivative()) ValueError: series precision must be finite for conversion to pari object.
In particular, sage is incapable of computing the discriminant of this *quadratic* polynomial! I'll shortly post a patch that catches this error and uses the sylvester matrix instead.
Attachments (1)
Change History (22)
comment:1 Changed 6 years ago by
 Status changed from new to needs_review
comment:2 Changed 6 years ago by
 Status changed from needs_review to needs_work
Changed 6 years ago by
comment:3 Changed 6 years ago by
 Cc pbruin added
comment:4 followup: ↓ 7 Changed 6 years ago by
 Status changed from needs_work to needs_info
I noticed that this problem is also solved by #15601, which implements conversion to PARI for power series with infinite precision by converting them to polynomials.
There are probably other base rings that cannot be converted to PARI, so using sylvester_matrix()
as a last resort is probably still useful. It would be good to have another example that still fails after applying #15601.
comment:5 Changed 6 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:6 Changed 5 years ago by
My changes from ticket:16014#comment:2 make P.discriminant()
work.
comment:7 in reply to: ↑ 4 ; followup: ↓ 8 Changed 5 years ago by
Replying to pbruin:
It would be good to have another example that still fails after applying #15601.
sage: R.<x> = AA[] sage: (2*x^2 + 3*x + 5).discriminant() TypeError: no conversion of this ring to a Singular ring defined
Does this help, even though it's singular here and not pari? RIF
does the same. I haven't worked out yet which resultants get computed by pari and which by singular.
comment:8 in reply to: ↑ 7 ; followup: ↓ 9 Changed 5 years ago by
Replying to gagern:
Replying to pbruin:
It would be good to have another example that still fails after applying #15601.
sage: R.<x> = AA[] sage: (2*x^2 + 3*x + 5).discriminant() TypeError: no conversion of this ring to a Singular ring definedDoes this help, even though it's singular here and not pari?
RIF
does the same. I haven't worked out yet which resultants get computed by pari and which by singular.
This example still fails with the patch applied. There seems to be a different problem here, namely that the class of that polynomial inherits from Polynomial_singular_repr
, even though the base field does not have a conversion to Singular. The same error occurs when you replace PowerSeriesRing
by LaurentSeriesRing
in the original example.
comment:9 in reply to: ↑ 8 ; followup: ↓ 10 Changed 5 years ago by
Replying to pbruin:
There seems to be a different problem here, namely that the class of that polynomial inherits from
Polynomial_singular_repr
, even though the base field does not have a conversion to Singular.
polynomial_element_generic.Polynomial_generic_field
inherits from polynomial_singular_interface.Polynomial_singular_repr
. That inheritance was introduced in 35bb3ea from 2007. Unfortunately I can't see what kind of bug this was supposed to fix. It seems like a bad move to me, though, since that class clearly assumes that you can convert to singular without further checks.
comment:10 in reply to: ↑ 9 ; followup: ↓ 11 Changed 5 years ago by
Replying to gagern:
Replying to pbruin:
There seems to be a different problem here, namely that the class of that polynomial inherits from
Polynomial_singular_repr
, even though the base field does not have a conversion to Singular.
polynomial_element_generic.Polynomial_generic_field
inherits frompolynomial_singular_interface.Polynomial_singular_repr
. That inheritance was introduced in 35bb3ea from 2007.
That commit only changed the order of the superclasses; the inheritance was there before.
Unfortunately I can't see what kind of bug this was supposed to fix. It seems like a bad move to me, though, since that class clearly assumes that you can convert to singular without further checks.
I agree that it is strange for polynomials over arbitrary fields to inherit from that class. An alternative would be to "manually" prescribe this inheritance for polynomials over fields that support conversion to Singular, but that doesn't sound very attractive. Another alternative would be to move resultant()
to a more generic polynomial class that first tries to use Singular and uses a generic Python implementation in case that fails.
comment:11 in reply to: ↑ 10 Changed 5 years ago by
Replying to pbruin:
That commit only changed the order of the superclasses; the inheritance was there before.
Thanks, I missed that fact.
I agree that it is strange for polynomials over arbitrary fields to inherit from that class. An alternative would be to "manually" prescribe this inheritance for polynomials over fields that support conversion to Singular, but that doesn't sound very attractive.
I see how the constructor of PolynomialRing_field checks for singular support and sets the _has_singular
property accordingly. We could use that place to change element_class
in a suitable way. But if we wanted to handle this using different classes, we'd add one more point to the already dense network of generic vs. special, domain vs. field, sparse vs. dense. Not sure I like that either.
Another alternative would be to move
resultant()
to a more generic polynomial class that first tries to use Singular and uses a generic Python implementation in case that fails.
Sounds good. As a first step, we could change Polynomial_singular_repr to check self.parent()._has_singular
and call super
if that isn't set. We could then make sure that Polynomial.resultant falls back to sylvester_matrix
if PARI doesn't work. Although I don't know yet for which rings PARI *will* work. Messy business…
comment:12 Changed 5 years ago by
 Branch set to u/pbruin/15061resultant
 Cc pbruin removed
 Commit set to d1a25de7d398d83dd7aee240b84665648483e279
 Status changed from needs_info to needs_review
 Summary changed from Pari can't handle all polynomial resultants to PARI and Singular can't handle all polynomial resultants
I think I have found a solution that will solve most of these problems. In this branch:
 Rob Harron's patch, with minor modifications.
 Remove
lcm()
andresultant()
fromPolynomial_singular_repr
. Forlcm()
, delete the code and move the doctests to the existingMPolynomial_libsingular.lcm()
; forresultant()
, move the code and doctests to the newMPolynomial_polydict.resultant()
.  In
MPolynomial_polydict.resultant()
, fall back on Sylvester matrices if the ring has no Singular implementation.  Various cosmetic fixes.
comment:13 Changed 5 years ago by
 Commit changed from d1a25de7d398d83dd7aee240b84665648483e279 to 51523b10dd11ba8e7b0689b351130e7596decc23
Branch pushed to git repo; I updated commit sha1. New commits:
51523b1  Trac 15061: delete an irrelevant doctest

comment:14 followups: ↓ 15 ↓ 16 Changed 5 years ago by
Judging from the timestamps, your system clock is wrong. Apart from that, I like the code, from what I can tell at first glance. Thanks! Will pull and run tests soon.
comment:15 in reply to: ↑ 14 Changed 5 years ago by
Replying to gagern:
Judging from the timestamps, your system clock is wrong.
I know, but it is a system that I am not the administrator of.
Apart from that, I like the code, from what I can tell at first glance. Thanks! Will pull and run tests soon.
OK, thanks!
comment:16 in reply to: ↑ 14 ; followup: ↓ 17 Changed 5 years ago by
Will pull and run tests soon.
All tests in src/sage/rings
passed here. And the code still looks sane at second glance. Am I qualified to give this a positive review?
comment:17 in reply to: ↑ 16 ; followup: ↓ 18 Changed 5 years ago by
Replying to gagern:
All tests in
src/sage/rings
passed here. And the code still looks sane at second glance. Am I qualified to give this a positive review?
You can probably judge yourself if you have done the things suggested in Reviewing Patches in the developer guide. (Note in particular that you are supposed to run all doctests; things can really break in unexpected places.)
comment:18 in reply to: ↑ 17 ; followup: ↓ 19 Changed 5 years ago by
 Reviewers set to Martin von Gagern
 Status changed from needs_review to positive_review
Replying to pbruin:
You can probably judge yourself if you have done the things suggested in Reviewing Patches in the developer guide.
./sage t all long
: done, no new errorsmake
including documentation: done./sage docbuild reference pdf
: done./sage coverage src/sage/rings/polynomial/*.py{,x}
: Diff shows that this now has 6 things less to complain about, and no new ones
I wonder whether the docs for resultant
regarding “Implemented using PARI’s polresultant function.” should get adjusted. On the other hand, I doubt that detailing the possible choices of algorithm is worth the effort.
(Note in particular that you are supposed to run all doctests; things can really break in unexpected places.)
Did so, and found #16285 in the process. But that's reproducible without your change, so not your fault.
Shouldn't running the testsuite be handled by patchbot? Or hasn't that been migrated to the git workflow yet?
comment:19 in reply to: ↑ 18 Changed 5 years ago by
Replying to gagern:
Shouldn't running the testsuite be handled by patchbot? Or hasn't that been migrated to the git workflow yet?
It has, but not enough people are running patchbots, and I think there are also some glitches that sometimes prevent it from doing its job.
comment:20 Changed 5 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:21 Changed 5 years ago by
 Branch changed from u/pbruin/15061resultant to 51523b10dd11ba8e7b0689b351130e7596decc23
 Resolution set to fixed
 Status changed from positive_review to closed
There's something wrong with the patch because of some whitespace issues. I'll fix this soon.