On 9/19/07, Joel B. Mohler <[EMAIL PROTECTED]> wrote: > As I wrote on sage-devel a bit earlier, I had some polynomials that were > causing singular gcd to slow down dramatically. I had thought this was > inconsistent, but upon more investigation it seems very consistent (on two > different computers). > > Here's some singular code to illustrate the problem. The first one computes > the gcd slowly, but not too bad (several seconds). > http://sage.math.washington.edu/home/jbmohler/gcd_fast.singular > This one takes a long time on my computer (at least a couple of minutes). > http://sage.math.washington.edu/home/jbmohler/gcd_slow.singular > Those time indications are on a P4 2.4 ghz. Memory usage of the Singular > executable is listed in 'top' at 12 MB (which seems perfectly reasonable to > me). Note also that mathematica (on sage.math) can write the ratio of these > polynomials in reduced form with-in a second (I'm supposing it computes a gcd > on the way to doing this).
Just for clarity, why not just compute the GCD with mathematica? Anyway, I'm more familiar with Magma, so I computed the above GCD that is slow in Sage with Magma and it takes 0.08 seconds. http://sage.math.washington.edu/home/was/tmp/g.m The answer gcd is: x0*x1*x3^2*x4^2*x5^2 - x0*x1*x3*x4*x5 - x3*x4*x5 + 1 What algorithm does Singular use for GCD's over QQ? If you take the slow Singular script you posted and change the characteristic from 0 to some prime number, e.g., 389, then the calculation in Singular is... interestingly, exactly 0.08 seconds too (identical to Magma). This suggests Magma is using a modular algorithm for polynomial gcd over QQ, but Singular isn't. it would be nice if somebody who actually knows something about multivariate gcd's could comment on options for modular algorithms, since we could just implement one in Sage on top of Singular's blazingly fast mod-p GCD code. > I computed the semi-random polynomials from this python script: > http://sage.math.washington.edu/home/jbmohler/singular_vs_mathematica.py > > Basically, they are products of binomials of the form > (1-{x0}^{e0}*...*{xn}^{en}) > where the {ei} are chosen randomly from {0,1}. I multiply about 8-12 of these > together to get polynomials of approximately 2^8 to 2^12 monomials. There is > a huge speed difference between n=4 and n=5 (5 variables vs. 6 variables). > > It also seems to make a difference if I select my {ei} from a larger set (say > {0,1,...,10}). This seems to be significantly faster (I'm guessing it's > because the gcd is of lower degree). > > I've now reproduced this with the singular that is built from sage and also > with a singular build from the singular website (3.0.3-ix86-Linux). > > Thanks > Joel > > > > -- William Stein Associate Professor of Mathematics University of Washington http://wstein.org --~--~---------~--~----~------------~-------~--~----~ 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/ -~----------~----~----~----~------~----~------~--~---
