On Sep 19, 5:37 pm, "Joel B. Mohler" <[EMAIL PROTECTED]> wrote:
> On Wednesday 19 September 2007 16:22, William Stein wrote:
>
> > 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.
>
> I'll be looking into implementing that. It makes me disgruntled to be at the
> mercy of mathematica (or pick your favorite big commercial m). :D.
>
> --
> Joel
Careful to check the papers. The Moses, et al. paper for singular
shows that Brown's method is ineffective for your problem, and it is
reasonably likely that this modified Brown method of Kaltofen et al.
is also ineffective. The Kaltofen, et al. paper avoids the question
of exponential runtime by restricting to bivariate dense polynomials.
The Wang paper describes one major improvement in a reasonable common
corner case for singular's algorithm. One presumes singular can be
asked to describe what it is doing during its EZ-GCD calculation, and
you can check if you are in this corner case. Wang's EEZ-GCD may be
the better solution, and one should be able to implement a prototype
of this quickly in the singular language. At any rate, it may be
better to look for improvements to EZ-GCD than for the modular gcd.
--~--~---------~--~----~------------~-------~--~----~
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/
-~----------~----~----~----~------~----~------~--~---
