modular resultants for multivariate polynomials over QQ

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

CC: @burcin @sagetrac-fschulze @videlec @jdemeyer

Component: algebra

Keywords: resultant, discriminant, polynomial, multivariate, sd35

Author: Frédéric Chapoton

Branch/Commit: u/chapoton/12174 @ 8952571

Issue created by migration from https://trac.sagemath.org/ticket/12174

[saraedum]

hack of a modular discriminant/resultant algorithm

[saraedum]

comment:1

Attachment: disc.sage.gz

[saraedum]

Changed keywords from resultant, discriminant, polynomial, multivariate to resultant, discriminant, polynomial, multivariate, sd35

[saraedum]

comment:6

See #16749 for a similar issue.

[saraedum]

comment:8

Still slow in 2018 btw.

[fchapoton]

Commit: 526d0d5

[fchapoton]

Branch: u/chapoton/12174

[fchapoton]

New commits:

526d0d5

trying to make a faster discriminant for polynomials in several vars

[fchapoton]

Author: Frédéric Chapoton

[fchapoton]

comment:10

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

[fchapoton]

comment:12

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

[videlec]

comment:13

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

[tscrim]

comment:14

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

[mantepse]

comment:15

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

[embray]

comment:20

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

[fchapoton]

comment:21

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.

[embray]

comment:23

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

[embray]

comment:24

Ticket retargeted after milestone closed

[mkoeppe]

comment:25

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.

[mkoeppe]

comment:27

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

[mkoeppe]

comment:28

Setting a new milestone for this ticket based on a cursory review.