Hi Roman! Sorry, I just saw the first problem. The coefficients for each bucket are disabled at the moment. We put some work in it, but we had the problem, that every modification to Singular: Polynomial ring over rings (instead fields), noncommutative polynomial rings (this was the guilty one) had its own routines accessing buckets, which were at some point incompatible with that. Then we gave up, since for our normal use cases, the coefficients only had very subtle effect.
Thank you for your comments on Singular. Naming this weak points hopefully leads to improvements. I think that the leading term of g is not normalized during pseudo division, but that would have to be checked. Best regards. Michael On 2 Apr., 09:39, Roman Pearce <[EMAIL PROTECTED]> wrote: > 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 > inhttp://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 -~----------~----~----~----~------~----~------~--~---
