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:  sage9.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: 
Description (last modified by )
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^62*a2^3*t^6*d+18*a1*a2*a3*t^6*d6*a1*a2*t^6*d^2+12*a0*t^6*d^3+3*a2^4*t^5+6*a1*a2^2*a3*t^59*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^26*a0*a2*t^5*d^2+6*a1*a2^3*t^46*a1^2*a2*a3*t^4+6*a0*a2^2*a3*t^418*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^34*a1^3*a3*t^312*a0*a1*a2*a3*t^39*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^212*a0*a1^2*a3*t^26*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*t12*a0^2*a1*a3*t+24*a0^2*a1*t*d4*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)
Change History (28)
Changed 9 years ago by
comment:1 Changed 9 years ago by
 Description modified (diff)
comment:2 Changed 9 years ago by
 Keywords sd35 added
comment:3 Changed 8 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:4 Changed 7 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:5 Changed 7 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:6 Changed 7 years ago by
See #16749 for a similar issue.
comment:7 Changed 7 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:8 Changed 3 years ago by
Still slow in 2018 btw.
comment:9 Changed 2 years ago by
 Branch set to u/chapoton/12174
 Cc vdelecroix added
 Commit set to 526d0d5a73147664e5625247e17961e281d26118
 Status changed from new to needs_review
New commits:
526d0d5  trying to make a faster discriminant for polynomials in several vars

comment:10 Changed 2 years ago by
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
 Milestone changed from sage6.4 to sage8.7
comment:12 Changed 2 years ago by
 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
Sided note: in the development version of flint there are multivariable polynomials and an implementation of discriminant.
comment:14 Changed 2 years ago by
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
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
 Commit changed from 526d0d5a73147664e5625247e17961e281d26118 to 576aaa1e8b4ab76cd38c11925a03658b1be2a912
Branch pushed to git repo; I updated commit sha1. New commits:
576aaa1  trac 12174 adding fricas (and placeholder for flint)

comment:17 Changed 2 years ago by
 Commit changed from 576aaa1e8b4ab76cd38c11925a03658b1be2a912 to a709faa4df9e94d79464be9e4c4b56a9ca9c6d39
Branch pushed to git repo; I updated commit sha1. New commits:
a709faa  trac 12174 reviewer suggestion for pari import

comment:18 Changed 2 years ago by
 Commit changed from a709faa4df9e94d79464be9e4c4b56a9ca9c6d39 to 8952571d427ac94f91ca90c8c9b5619bbf60ce4d
comment:19 Changed 2 years ago by
some progress..
comment:20 Changed 2 years ago by
 Milestone changed from sage8.7 to sage8.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
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
 Status changed from needs_review to needs_work
comment:23 Changed 2 years ago by
 Milestone changed from sage8.8 to sage8.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
 Milestone changed from sage8.9 to sage9.1
Ticket retargeted after milestone closed
comment:25 Changed 13 months ago by
 Milestone changed from sage9.1 to sage9.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
 Milestone changed from sage9.2 to sage9.3
comment:27 Changed 3 months ago by
 Milestone changed from sage9.3 to sage9.4
Setting new milestone based on a cursory review of ticket status, priority, and last modification date.
hack of a modular discriminant/resultant algorithm