On Apr 1, 11:36 pm, Michael Brickenstein <[EMAIL PROTECTED]> wrote: > I don't find it very impressive, posting some benchmark for just one > example.
There are 4 benchmarks in http://www.cecm.sfu.ca/~rpearcea/sdmp/2008_04_01/benchmarks.txt 6376 x 46376 = 635376 terms (dense, 4 variables) 26599 x 36365 = 19631157 terms (sparse, 10 variables) 6188 x 6188 = 5821335 terms (very sparse, 5 variables) 531441 / 15625 terms = 15625 quotient + 515816 remainder (dense, 6 variables) The last one is a pseudo-division, and Singular messed up. I bet it scales the entire dividend every time something is merged into the geobucket, or whenever the leading term of the geobucket is computed. This could be easily fixed. Otherwise Singular performed very well on the division benchmarks. Also, while I'm on the topic of Singular's geobucket implementation, I looked at the code and it looks like there are buckets for each coefficient ? I'm not sure. Anyways, you should store a denominator for each bucket, and integer coefficients in the polynomials. Then store a multiplier for each bucket that you use to merge leading terms. For a pseudo-division f / g = (q,r) that would give you N*log N multiplications in Z, where N = f + q*g. That's not as good as my implementation, but it would perform well in practice. > Note, that the example is dense. > If he is using fast (Strassen-like) algorithms, then it is quite > natural, to achieve > good results in these problems. I can assure you, for an n x m multiplication we multiply, sort, and merge n*m products of terms. The sorting is O(n*m*log(min(n,m))). For a division f/g = (q,r), the sorting is O(f + q*g*log(min(q,g))) comparisons, whereas I believe geobuckets are N*log N where N = f + q*g in the worst case and N*log(g) on average. Also I would like to credit the Singular group for designing the fast packed monomial representations that I use (with modifications). That is in the paper of course. --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
