tag:blogger.com,1999:blog-7651115430416156636.post8674871352553218087..comments2017-09-24T06:12:02.323-07:00Comments on Reading, Writing and Arithmetic: Update on fast multivariate polynomial arithmetic in FlintWilliam Harthttp://www.blogger.com/profile/18416881057216462316noreply@blogger.comBlogger12125tag:blogger.com,1999:blog-7651115430416156636.post-67372758947804743672017-07-12T05:56:58.472-07:002017-07-12T05:56:58.472-07:00Bernard Parisse helped me track down why the spars...Bernard Parisse helped me track down why the sparse quotient only times for Flint looked so ridiculously low. In fact, due to an interfacing issue between Nemo and Flint, I was inadvertently using reflected lexicographical ordering instead of true lexicographical ordering, which affected this benchmark. The timings have been corrected above, and indeed, the Flint timings now look much more reasonable.William Harthttps://www.blogger.com/profile/18416881057216462316noreply@blogger.comtag:blogger.com,1999:blog-7651115430416156636.post-44899096959061622952017-07-10T13:42:49.941-07:002017-07-10T13:42:49.941-07:00So, representation matters. Using Trip-1.4.0's...So, representation matters. Using Trip-1.4.0's POLPV (one of their dense representations) the dense timing becomes:<br /><br />Dense Multiplication: n = 30: 41s<br /><br />The best representation for the sparse case seems to be the POLYV representation which I originally used, so that timing remains:<br /><br />Sparse Multiplication: n = 16: 37sWilliam Harthttps://www.blogger.com/profile/18416881057216462316noreply@blogger.comtag:blogger.com,1999:blog-7651115430416156636.post-33805037712604241272017-07-10T13:14:30.413-07:002017-07-10T13:14:30.413-07:00Mickael Gastineau said it is fine to use Trip for ...Mickael Gastineau said it is fine to use Trip for timings. Trip 1.4.0 works fine on my machine. I already made some silly mistakes trying to time things, so I will add full timing results at a later date when I am more familiar with the system.<br /><br />For now, here are the Trip-1.4.0 timing results on the same machine as the above timings:<br /><br />Dense Multiplication: n = 30: 50s<br />Sparse Multiplication: n = 16: 37s<br /><br />However, Trip has multiple different representations and the right one should be selected for the particular problem, so these timings are unofficial until I've had time to check everything carefully.<br /><br />Note that Trip scales very well with the number of cores, so will be quite hard to beat on parallel timings I believe.William Harthttps://www.blogger.com/profile/18416881057216462316noreply@blogger.comtag:blogger.com,1999:blog-7651115430416156636.post-83335031362211850202017-07-10T12:16:59.272-07:002017-07-10T12:16:59.272-07:00I have written to one of the authors of Trip to as...I have written to one of the authors of Trip to ask permission to use the academic version for timings, and to see if this is the latest version. But I don't feel comfortable publishing timings for it at the moment, since I don't know how to use it. Perhaps in a later blog I will do so. It's not even clear if it will run on my machine, so we will see.William Harthttps://www.blogger.com/profile/18416881057216462316noreply@blogger.comtag:blogger.com,1999:blog-7651115430416156636.post-69940509792316141372017-07-10T11:48:38.269-07:002017-07-10T11:48:38.269-07:00Here you go:
http://www.imcce.fr/fr/presentation/...Here you go:<br /><br />http://www.imcce.fr/fr/presentation/equipes/ASD/trip/trip.html<br /><br />Note that some limited version of Trip is available for download. But I don't know what "limited" means. I'd hesitate to publish timings based on that. Also, I don't know if publishing benchmarks is considered "academic research".William Harthttps://www.blogger.com/profile/18416881057216462316noreply@blogger.comtag:blogger.com,1999:blog-7651115430416156636.post-16940151870082671632017-07-10T11:17:13.011-07:002017-07-10T11:17:13.011-07:00it would be good to include links to packages you ...it would be good to include links to packages you are talking about, at least more exotic ones. E.g. Trip is very hard to google...dimpasehttps://www.blogger.com/profile/14596969929730094920noreply@blogger.comtag:blogger.com,1999:blog-7651115430416156636.post-64567198013680821222017-07-10T10:26:12.966-07:002017-07-10T10:26:12.966-07:00Oh, I should add that the coefficients don't g...Oh, I should add that the coefficients don't get very large in these examples. It's the number of terms in the result that is the main reason for the long periods of time. For example, in the sparse case there are over 28 million terms in the product polynomials.William Harthttps://www.blogger.com/profile/18416881057216462316noreply@blogger.comtag:blogger.com,1999:blog-7651115430416156636.post-1838975920878985092017-07-10T10:23:10.002-07:002017-07-10T10:23:10.002-07:00We'll keep that in mind for the next iteration...We'll keep that in mind for the next iteration, Andrew. We currently haven't got code over Z/pZ, and it might be interesting to do comparisons with especially larger numbers of variables.William Harthttps://www.blogger.com/profile/18416881057216462316noreply@blogger.comtag:blogger.com,1999:blog-7651115430416156636.post-57824864848806379172017-07-10T02:52:21.304-07:002017-07-10T02:52:21.304-07:00Impressive timings!
I'd be curious to see a s...Impressive timings!<br /><br />I'd be curious to see a similar comparison over Z/pZ, say with p=2,p=3, p~2^30, p~2^60. This would presumably also let you test with larger values of n in a reasonable amount of time.<br /><br />It would also be interesting to see tests involving different numbers of variables (e.g. 1,2,4,8,16).<br />Andrew Sutherlandhttps://www.blogger.com/profile/06264256964561491338noreply@blogger.comtag:blogger.com,1999:blog-7651115430416156636.post-43956665775936384162017-07-10T02:22:03.162-07:002017-07-10T02:22:03.162-07:00Ah, I see this blog doesn't like the Sage code...Ah, I see this blog doesn't like the Sage code format. Of course I had angled brackets and four variables in the brackets. But divides doesn't compute the quotient, so I can't use that for the benchmark I have given. The other timings you give are consistent with what I have. Your machine is a little faster than mine.William Harthttps://www.blogger.com/profile/18416881057216462316noreply@blogger.comtag:blogger.com,1999:blog-7651115430416156636.post-84894338354578029552017-07-10T02:17:33.104-07:002017-07-10T02:17:33.104-07:00I used R. = PolynomialRing(ZZ, 4)
Is this not the...I used R. = PolynomialRing(ZZ, 4)<br /><br />Is this not the dedicated polynomial rings?William Harthttps://www.blogger.com/profile/18416881057216462316noreply@blogger.comtag:blogger.com,1999:blog-7651115430416156636.post-33802859673124847722017-07-09T22:56:14.474-07:002017-07-09T22:56:14.474-07:00Hello Bill, it is likely you used the symbolic rin...Hello Bill, it is likely you used the symbolic ring in Sage, not the dedicated polynomial rings. For example with the "Divisibility test with quotient (sparse)" and n=6 I get:<br /><br />sage: R.=PolynomialRing(ZZ)<br />sage: f = (1 + x + y + 2*z^2 + 3*t^3 + 5*u^5)^6<br />sage: g = (1 + u + t + 2*z^2 + 3*y^3 + 5*x^5)^6<br />sage: p = f*g<br />sage: %timeit f.divides(p)<br />10 loops, best of 3: 110 ms per loop<br /><br />or multiplication:<br /><br />sage: R.=PolynomialRing(ZZ)<br />sage: f = (1 + x + y + 2*z^2 + 3*t^3 + 5*u^5)^6<br />sage: g = (1 + u + t + 2*z^2 + 3*y^3 + 5*x^5)^6<br />sage: %timeit _ = f*g<br />10 loops, best of 3: 90.3 ms per loop<br />Ralf Stephanhttps://www.blogger.com/profile/18267577618598521684noreply@blogger.com