Hi (I'm sending this to sage-devel as well -- there's a bunch of interest there to get our multivariate stuff up to speed),
I've put some examples of things that are slow up at http://sage.math.washington.edu/home/jbmohler/singular/ These are things that I ran into just this morning in my computations. I will try and add more examples in this directory over the next couple of days. I found an example today of a polynomial division that took at least 10 minutes -- I wasn't patient enough to wait it out. Everything I could think of off the top of my head right now seemed very similar to what I had. I'm working with two types of polynomials: 1) Large irreducible ones where all coefficients are one. I often specialize a variable or two (or more) and then try and factor the result (coefficients may no longer be one). 2) Products of a bunch of binomials (again the coefficients are small). I'm working with fractions of polynomials like 1) divided by 2). (If you are curious, they come from http://sporadic.stanford.edu/bump/wmd2.ps and following papers.) I have a whole family of rational functions like this, but they all look very similar so I'm not sure how useful they will be for generating ideas for tuning. It seems like the same heuristic might work for all of them. Thanks Joel On Wed, Dec 05, 2007 at 10:11:53AM +0100, [EMAIL PROTECTED] wrote: > > > > On Monday 03 December 2007 06:05, you wrote: > > > The gcd is (by default) ezgcd (from factory/fac_ezgcd.cc) > > > which substitutes random values into all but one variable and tries > > > to lift the univariate gcd to the real one. > > > This could be improved by a better heuristic for the main variable. > > > > I'm curious about one thing with this. About a month ago you had > > introduced a > > multi-modular algorithm for computing gcds when I reported slow gcd > > computations. We've switched to the multi-modular algorithm in sage via > > libSingular with great success. In my case it was 10 or 20 times faster or > > maybe even more (I forget). Would it be better to use the multi-modular > > gcd > > algorithm in the factoring? Perhaps I have strange polynomials -- I could > > provide many more like them for testing if you are interested :). > > > > -- > > Joel > > > Currently (Singular 3-0-4), the strategy for gcd of multivariate polynomials > in characteristic 0 is as follows: > 1) if isOn(SW_USE_EZGCD) try ezgcd(f,g) > if ezgcd_special_case, try variant 2 > else > try variant 2 > 2) if isOn(SW_USE_CHINREM_GCD) try multi-modular gcd (chinrem_gcd(f,g)) > if not enough good primes (we try from a finite pre-defined list) > try variant 3 > else > try variant 3 > 3) a generic, slow gcd implementation based on pseudo remainder > > Before the introduction of the multi-modular gcd the variant 2 was missing: > if one meets the "special case" of ezgcd, gcd became a slow algorithm. > We also tried to use first variant 2 than 1 and 3: on our tests > it was slightly slower (maybe here a good heuristic may help). > > By default, both switches ( SW_USE_EZGCD and SW_USE_CHINREM_GCD) > are on. To chage this, use the Singular command > system("gcd","EZGCD",0); resp. > system("gcd","CRGCD",0); > > So not most of the time is spent in gcd computations. > Nevertheless, I am interessted in getting nice examples > to get ideas about better heuristics. > > Hans --~--~---------~--~----~------------~-------~--~----~ 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://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~----------~----~----~----~------~----~------~--~---
