Re: [sage-devel] Re: [ODK participants] Blog post on fast multivariate arithmetic

On Tuesday, 11 July 2017 20:26:51 UTC+2, Johan S. H. Rosenkilde wrote: > > > That's absolutely correct, and a point I make in my blog. One heuristic > is > > that GBs tend to have a large number of very small polynomials and so > one > > can dispatch larger arithmetic operations to a differen

Re: [sage-devel] Re: [ODK participants] Blog post on fast multivariate arithmetic

> That's absolutely correct, and a point I make in my blog. One heuristic is > that GBs tend to have a large number of very small polynomials and so one > can dispatch larger arithmetic operations to a different back end safely > (converting to and from some other format on the fly). This is som

Re: [sage-devel] Re: [ODK participants] Blog post on fast multivariate arithmetic

On Monday, 10 July 2017 17:05:10 UTC+2, vdelecroix wrote: > > On 10/07/2017 16:36, 'Bill Hart' via sage-devel wrote: > >> BTW, it would be good to have them in the post! > >> > > > > It already says in the post that for systems that didn't provide the > > required function, I used quotient w

Re: [sage-devel] Re: [ODK participants] Blog post on fast multivariate arithmetic

Switching to Singular for working over ZZ seems like a good idea. I timed it over ZZ and QQ in Singular and don't notice much difference in the timings. I'm sure the following is obvious, but let me mention it just in case. In the blog post I explain that some systems do not explicitly provide

Re: [sage-devel] Re: [ODK participants] Blog post on fast multivariate arithmetic

On 10/07/2017 16:36, 'Bill Hart' via sage-devel wrote: BTW, it would be good to have them in the post! It already says in the post that for systems that didn't provide the required function, I used quotient with remainder. I meant code snippets. -- You received this message because you are

Re: [sage-devel] Re: [ODK participants] Blog post on fast multivariate arithmetic

On Monday, 10 July 2017 13:31:26 UTC+2, vdelecroix wrote: > > On 10/07/2017 12:48, mmarco wrote: > > It is surprising the difference between singular and Sage, considering > that > > Sage mostly relies on Singular for multivariate polynomial arithmetic. > In > > the case of divisions, I susp

Re: [sage-devel] Re: [ODK participants] Blog post on fast multivariate arithmetic

Sorry, I meant (f*g).expand(). It's even slower, interesting. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to t

Re: [sage-devel] Re: [ODK participants] Blog post on fast multivariate arithmetic

On Monday, July 10, 2017 at 8:55:23 AM UTC+2, vdelecroix wrote: > > He was certainly not using the awfully slow symbolic ring > > sage: x,y,z,t,u = SR.var('x,y,z,t,u') > sage: f = (1 + x + y + 2*z^2 + 3*t^3 + 5*u^5)^6 > sage: g = (1 + u + t + 2*z^2 + 3*y^3 + 5*x^5)^6 > sage: %time h = (f*g).exp

Re: [sage-devel] Re: [ODK participants] Blog post on fast multivariate arithmetic

This is now #23395 El lunes, 10 de julio de 2017, 13:43:46 (UTC+2), mmarco escribió: > > If you used quo_rem, beware that Sage only uses Singular if the > coefficient ring is a field. So if you define your polynomials over QQ > instead of ZZ you will get

Re: [sage-devel] Re: [ODK participants] Blog post on fast multivariate arithmetic

If you used quo_rem, beware that Sage only uses Singular if the coefficient ring is a field. So if you define your polynomials over QQ instead of ZZ you will get timings similar to those of Singular. In the case of ZZ, it will do so with some generic python implementation of division. I guess w

Re: [sage-devel] Re: [ODK participants] Blog post on fast multivariate arithmetic

If you used quo_rem, beware that Sage only uses Singular if the coefficient ring is a field. So if you define your polynomials over QQ instead of ZZ you will get timings similar to those of Singular. In the case of ZZ, it will do so with some generic python implementation of division. I guess w

Re: [sage-devel] Re: [ODK participants] Blog post on fast multivariate arithmetic

On 10/07/2017 12:48, mmarco wrote: It is surprising the difference between singular and Sage, considering that Sage mostly relies on Singular for multivariate polynomial arithmetic. In the case of divisions, I suspect that it has to do with the fact that Sage treats division of polynomials as an

Re: [sage-devel] Re: [ODK participants] Blog post on fast multivariate arithmetic

It is surprising the difference between singular and Sage, considering that Sage mostly relies on Singular for multivariate polynomial arithmetic. In the case of divisions, I suspect that it has to do with the fact that Sage treats division of polynomials as an operation in the fraction field, s

Re: [sage-devel] Re: [ODK participants] Blog post on fast multivariate arithmetic

The reason that I required the quotient as well in the divisibility benchmark was that Magma does the n = 20 dense case in 0.15s otherwise, and I don't believe it is possible to do it that fast if you aren't doing it heuristically, as I explained in the blog post. Therefore, all the systems tim

Re: [sage-devel] Re: [ODK participants] Blog post on fast multivariate arithmetic

7.6 On Monday, 10 July 2017 11:56:32 UTC+2, vdelecroix wrote: > > On 10/07/2017 09:34, Ralf Stephan wrote: > > On Monday, July 10, 2017 at 8:55:23 AM UTC+2, vdelecroix wrote: > >> > >> He was certainly not using the awfully slow symbolic ring > >> > > > > Then his slow timings for e.g. "Divi

Re: [sage-devel] Re: [ODK participants] Blog post on fast multivariate arithmetic

On 10/07/2017 09:34, Ralf Stephan wrote: On Monday, July 10, 2017 at 8:55:23 AM UTC+2, vdelecroix wrote: He was certainly not using the awfully slow symbolic ring Then his slow timings for e.g. "Divisibility test with quotient (sparse)" needs a different explanation. Sage version? -- You

Re: [sage-devel] Re: [ODK participants] Blog post on fast multivariate arithmetic

Because it is "divisibility test with quotient", not "divisibility test". It is equivalent to calling Magma's "IsDivisibleBy" with two return arguments. On Monday, 10 July 2017 09:34:39 UTC+2, Ralf Stephan wrote: > > On Monday, July 10, 2017 at 8:55:23 AM UTC+2, vdelecroix wrote: >> >> He was ce

Re: [sage-devel] Re: [ODK participants] Blog post on fast multivariate arithmetic

On Monday, July 10, 2017 at 8:55:23 AM UTC+2, vdelecroix wrote: > > He was certainly not using the awfully slow symbolic ring > Then his slow timings for e.g. "Divisibility test with quotient (sparse)" needs a different explanation. -- You received this message because you are subscribed to th

Re: [sage-devel] Re: [ODK participants] Blog post on fast multivariate arithmetic

He was certainly not using the awfully slow symbolic ring sage: x,y,z,t,u = SR.var('x,y,z,t,u') sage: f = (1 + x + y + 2*z^2 + 3*t^3 + 5*u^5)^6 sage: g = (1 + u + t + 2*z^2 + 3*y^3 + 5*x^5)^6 sage: %time h = (f*g).expand() CPU times: user 8.99 s, sys: 25.7 ms, total: 9.01 s Wall time: 9.01 s ver