On Sep 19, 9:55 pm, "William Stein" <[EMAIL PROTECTED]> wrote:
> 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.
>
Well, we had some more discussion in #sage-devel and rpw posted an
interesting link:
http://magma.maths.usyd.edu.au/users/allan/gcdcomp.html
In summary: Singular's multivariate GCD is slower by orders of
magnitude. Magma's algorithms are described at:
http://www.msri.org/about/computing/docs/magma/html/text587.htm
I don't know how current the documentation is, though.
Cheers,
Michael
>
>
> > 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 Washingtonhttp://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/
-~----------~----~----~----~------~----~------~--~---
