On 9/19/07, mabshoff
<[EMAIL PROTECTED]> > 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.
I think those timings are way out of date, since Singular 3 seems
to be *very* fast at mod p multivariate GCD computation, even
though it sucks over QQ. Check out this paper:
http://www.cecm.sfu.ca/CAG/papers/brown.ps
It on exactly the problem of GCD over QQ (or equiv ZZ),
and section 2 has a complete description of a gcd algorithm
that reduces gcd over ZZ to doing gcd's mod p.
Who wants to be a hero -- like Jon Bober and number of partitions --
and implement this for Sage, so that multivariate GCD's aren't
embarrassingly slow in Sage anymore? This slowness *has*
been something reported to me on several occasions during
the last 2 years:
http://trac.sagemath.org/sage_trac/ticket/696
William
--~--~---------~--~----~------------~-------~--~----~
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/
-~----------~----~----~----~------~----~------~--~---
