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: sage-6.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)

trac_15061_use_sylvester_matrix_for_resultant_when_pari_fails.patch (1.7 KB) - added by robharron 6 years ago.

Download all attachments as: .zip

Change History (22)

comment:1 Changed 6 years ago by robharron

  • Status changed from new to needs_review

comment:2 Changed 6 years ago by robharron

  • Status changed from needs_review to needs_work

There's something wrong with the patch because of some whitespace issues. I'll fix this soon.

comment:3 Changed 6 years ago by pbruin

  • Cc pbruin added

comment:4 follow-up: Changed 6 years ago by pbruin

  • 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 vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:6 Changed 5 years ago by gagern

My changes from ticket:16014#comment:2 make P.discriminant() work.

comment:7 in reply to: ↑ 4 ; follow-up: Changed 5 years ago by 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 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 ; follow-up: Changed 5 years ago by pbruin

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 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.

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 ; follow-up: Changed 5 years ago by 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 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 ; follow-up: Changed 5 years ago by pbruin

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 from polynomial_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 gagern

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…

Last edited 5 years ago by gagern (previous) (diff)

comment:12 Changed 5 years ago by pbruin

  • Authors set to Robert Harron, Peter Bruin
  • Branch set to u/pbruin/15061-resultant
  • 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() and resultant() from Polynomial_singular_repr. For lcm(), delete the code and move the doctests to the existing MPolynomial_libsingular.lcm(); for resultant(), move the code and doctests to the new MPolynomial_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 git

  • Commit changed from d1a25de7d398d83dd7aee240b84665648483e279 to 51523b10dd11ba8e7b0689b351130e7596decc23

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

51523b1Trac 15061: delete an irrelevant doctest

comment:14 follow-ups: Changed 5 years ago by gagern

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 pbruin

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 ; follow-up: Changed 5 years ago by gagern

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 ; follow-up: Changed 5 years ago by pbruin

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 ; follow-up: Changed 5 years ago by gagern

  • 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 errors
  • make 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 pbruin

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 vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:21 Changed 5 years ago by vbraun

  • Branch changed from u/pbruin/15061-resultant to 51523b10dd11ba8e7b0689b351130e7596decc23
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.