On Sep 19, 4:22 pm, "William Stein" <[EMAIL PROTECTED]> wrote: > 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
It might be better to contribute such a implementation directly to singular. The current singular implementation is described at: http://www.singular.uni-kl.de/Manual/latest/sing_32.htm as using the algorithm described in: http://doi.acm.org/10.1145/800192.805698 --~--~---------~--~----~------------~-------~--~----~ 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/ -~----------~----~----~----~------~----~------~--~---
