The times I get with the new code are 28s to K = 70 and 135s to K = 100. This is on an Opteron K102 though, which probably does the coefficient arithmetic a little faster than the core2. In fact much of the time is probably coefficient arithmetic in this problem I would guess. The coefficients must get pretty large pretty quick.
Bill. On 15 May, 21:03, William Stein <wst...@gmail.com> wrote: > On Sat, May 15, 2010 at 12:55 PM, Tom Coates <t.coa...@imperial.ac.uk> wrote: > > > Thank you (everyone!) for the many extremely helpful comments and > > links. > > > Recall that I need to compute > > > 1, f, f^2, ..., f^K > > > for f in ZZ[x,y,z] and K known but large. (In fact I only need > > certain coefficients of the f^i, but this does not seem to help very > > much.) > > I have implemented the most naive possible approach in Sage, MAGMA, > > and Maple, and also written C code that first encodes > > f as a univariate polynomial and then uses the flint library to do the > > multiplication. The results so far, for a typical f that occurs in my > > problem: > > > Sage: > > K=70 96.9 secs > > K=100 439.4 secs > > > MAGMA: > > K=70 42.9 secs > > K=100 191.7 secs > > 1. On what hardware? > > 2. Can you post something so that somebody else (e.g., me) could > replicate this benchmark? > I want to make sure that, e.g., your Sage wasn't built incorrectly. > > -- William > > > > > > > > > Also Sage uses almost twice the amount of memory as MAGMA (1587 Mb > > rather than 910 Mb for the K=100 case). My C code is substantially > > slower than either MAGMA or Sage. The Maple code is by far the > > slowest and uses the most memory, but this is not a fair comparison > > because at the moment I only have access to Maple 12 and this does not > > have the Johnson/Monaghan--Pearce algorithm available (this is in > > Maple 14, which I should have in a week or so) . Also I have very > > little experience with Maple and so I might be doing something > > stupid. All these timings are from the same machine, which has an > > Intel Core 2 CPU running at 2.4GHz. > > > More details on the problem. In my situation f starts off as a > > Laurent polynomial, but I convert it into an element of ZZ[x,y,z] by > > multiplying by an appropriate monomial. The original Laurent > > polynomial is "small and dense": its Newton polytope is a 3- > > dimensional reflexive polytope, so in particular has only one integer > > point in the interior (this interior point is the origin). Also the > > exponents are all quite close together: the Newton polytope of a > > typical f would fit in a 5x5x5 cube. > > > Again, many thanks for all of the advice. I look forward to trying > > out Bill's new code. > > > Best, > > > Tom > > > -- > > To post to this group, send an email to sage-devel@googlegroups.com > > To unsubscribe from this group, send an email to > > sage-devel+unsubscr...@googlegroups.com > > For more options, visit this group > > athttp://groups.google.com/group/sage-devel > > URL:http://www.sagemath.org > > -- > William Stein > Professor of Mathematics > University of Washingtonhttp://wstein.org > > -- > To post to this group, send an email to sage-devel@googlegroups.com > To unsubscribe from this group, send an email to > sage-devel+unsubscr...@googlegroups.com > For more options, visit this group athttp://groups.google.com/group/sage-devel > URL:http://www.sagemath.org -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
