Opened 9 years ago

Last modified 3 months ago

#12174 needs_work task

modular resultants for multivariate polynomials over QQ

Reported by: saraedum Owned by: AlexGhitza
Priority: minor Milestone: sage-9.4
Component: algebra Keywords: resultant, discriminant, polynomial, multivariate, sd35
Cc: burcin, fschulze, vdelecroix, jdemeyer Merged in:
Authors: Frédéric Chapoton Reviewers:
Report Upstream: N/A Work issues:
Branch: u/chapoton/12174 (Commits, GitHub, GitLab) Commit: 8952571d427ac94f91ca90c8c9b5619bbf60ce4d
Dependencies: Stopgaps:

Status badges

Description (last modified by saraedum)

Sage is somewhat slow when computing discriminants of multivariate polynomials:

sage: R.<a0,a1,a2,a3,d,t> = QQ[]
sage: f=(16/27)*(a3+d)^2*(3*a2^2*t^7*d^2+12*a1*t^7*d^3+4*a2^3*a3*t^6-2*a2^3*t^6*d+18*a1*a2*a3*t^6*d-6*a1*a2*t^6*d^2+12*a0*t^6*d^3+3*a2^4*t^5+6*a1*a2^2*a3*t^5-9*a1^2*a3^2*t^5+12*a1*a2^2*t^5*d+18*a1^2*a3*t^5*d+18*a0*a2*a3*t^5*d+3*a1^2*t^5*d^2-6*a0*a2*t^5*d^2+6*a1*a2^3*t^4-6*a1^2*a2*a3*t^4+6*a0*a2^2*a3*t^4-18*a0*a1*a3^2*t^4+18*a1^2*a2*t^4*d+12*a0*a2^2*t^4*d+36*a0*a1*a3*t^4*d+6*a0*a1*t^4*d^2+3*a1^2*a2^2*t^3+6*a0*a2^3*t^3-4*a1^3*a3*t^3-12*a0*a1*a2*a3*t^3-9*a0^2*a3^2*t^3+8*a1^3*t^3*d+36*a0*a1*a2*t^3*d+18*a0^2*a3*t^3*d+3*a0^2*t^3*d^2+6*a0*a1*a2^2*t^2-12*a0*a1^2*a3*t^2-6*a0^2*a2*a3*t^2+24*a0*a1^2*t^2*d+18*a0^2*a2*t^2*d+3*a0^2*a2^2*t-12*a0^2*a1*a3*t+24*a0^2*a1*t*d-4*a0^3*a3+8*a0^3*d)
sage: time d=f.discriminant(t)
Time: CPU 3101.66 s, Wall: 3101.78 s

Sage is relying on singular to compute the resultant of f and the derivative of f. Alternatively, one can compute the determinant of the Sylvester matrix; doing this mod p and using chinese remaindering then is much faster in this example:

sage: time dm=modular_discriminant(f,t)
Time: CPU 42.55 s, Wall: 42.55 s
sage: d==dm
True

I attached the implementation of modular_discriminant(). This should not go into sage like this, it's just some experiments I did. I haven't tested it or thought about it too carefully.

Btw. Maple 9.5 needs about 4s to compute this; a recent version of Maple was even faster, but I don't have the data here right now.

Attachments (1)

disc.sage (2.8 KB) - added by saraedum 9 years ago.
hack of a modular discriminant/resultant algorithm

Download all attachments as: .zip

Change History (28)

Changed 9 years ago by saraedum

hack of a modular discriminant/resultant algorithm

comment:1 Changed 9 years ago by saraedum

  • Description modified (diff)

comment:2 Changed 9 years ago by saraedum

  • Keywords sd35 added

comment:3 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:4 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:5 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:6 Changed 7 years ago by saraedum

See #16749 for a similar issue.

comment:7 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:8 Changed 3 years ago by saraedum

Still slow in 2018 btw.

comment:9 Changed 2 years ago by chapoton

  • Authors set to Frédéric Chapoton
  • Branch set to u/chapoton/12174
  • Cc vdelecroix added
  • Commit set to 526d0d5a73147664e5625247e17961e281d26118
  • Status changed from new to needs_review

New commits:

526d0d5trying to make a faster discriminant for polynomials in several vars

comment:10 Changed 2 years ago by chapoton

Some timings

sage: x,y,z=polygen(QQ,'x,y,z')
sage: f=x**55+x**33*z**4+3445*x*y*z*z
sage: %timeit f.discriminant(x,algorithm='singular')
10 loops, best of 3: 25.4 ms per loop
sage: %timeit f.discriminant(x)
100 loops, best of 3: 4.36 ms per loop
sage: g= f + 5234*x*y*z**66
sage: %timeit g.discriminant(x,algorithm='singular')
1 loop, best of 3: 14.3 s per loop
sage: %timeit g.discriminant(x)
1 loop, best of 3: 4.68 s per loop

comment:11 Changed 2 years ago by chapoton

  • Milestone changed from sage-6.4 to sage-8.7

comment:12 Changed 2 years ago by chapoton

  • Cc jdemeyer added

Not extremely convincing, sadly, for smaller polynomials. Maybe I am not doing it the right way ?

comment:13 Changed 2 years ago by vdelecroix

Sided note: in the development version of flint there are multivariable polynomials and an implementation of discriminant.

comment:14 Changed 2 years ago by tscrim

Maybe you want to use from sage.libs.all import pari? This is what polynomial_element.pyx does.

comment:15 Changed 2 years ago by mantepse

Not sure whether this is interesting, but I get (using the develop branch, that is, without this patch):

sage: x,y,z=polygen(QQ,'x,y,z')
sage: f=x**55+x**33*z**4+3445*x*y*z*z
sage: g = f + 5234*x*y*z**66
sage: g.discriminant(x)/fricas(g).discriminant(x).sage()
1
sage: %timeit g.discriminant(x)
1 loop, best of 3: 6.93 s per loop
sage: %timeit fricas(g).discriminant(x).sage()
1 loop, best of 3: 270 ms per loop

comment:16 Changed 2 years ago by git

  • Commit changed from 526d0d5a73147664e5625247e17961e281d26118 to 576aaa1e8b4ab76cd38c11925a03658b1be2a912

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

576aaa1trac 12174 adding fricas (and placeholder for flint)

comment:17 Changed 2 years ago by git

  • Commit changed from 576aaa1e8b4ab76cd38c11925a03658b1be2a912 to a709faa4df9e94d79464be9e4c4b56a9ca9c6d39

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

a709faatrac 12174 reviewer suggestion for pari import

comment:18 Changed 2 years ago by git

  • Commit changed from a709faa4df9e94d79464be9e4c4b56a9ca9c6d39 to 8952571d427ac94f91ca90c8c9b5619bbf60ce4d

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

cc76522Merge branch 'u/chapoton/12174' in 8.7.b7
8952571trac 12174 make the fricas choice work

comment:19 Changed 2 years ago by chapoton

some progress..

comment:20 Changed 2 years ago by embray

  • Milestone changed from sage-8.7 to sage-8.8

Ticket retargeted after milestone closed (if you don't believe this ticket is appropriate for the Sage 8.8 release please retarget manually)

comment:21 Changed 2 years ago by chapoton

With pari, for the large example in the ticket description:

sage: time d=f.discriminant(t)
CPU times: user 44min 8s, sys: 2.15 s, total: 44min 11s

so not so good after all.

comment:22 Changed 2 years ago by chapoton

  • Status changed from needs_review to needs_work

comment:23 Changed 2 years ago by embray

  • Milestone changed from sage-8.8 to sage-8.9

Tickets still needing working or clarification should be moved to the next release milestone at the soonest (please feel free to revert if you think the ticket is close to being resolved).

comment:24 Changed 17 months ago by embray

  • Milestone changed from sage-8.9 to sage-9.1

Ticket retargeted after milestone closed

comment:25 Changed 13 months ago by mkoeppe

  • Milestone changed from sage-9.1 to sage-9.2

Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.

comment:26 Changed 8 months ago by mkoeppe

  • Milestone changed from sage-9.2 to sage-9.3

comment:27 Changed 3 months ago by mkoeppe

  • Milestone changed from sage-9.3 to sage-9.4

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

Note: See TracTickets for help on using tickets.