Ha, yep, stupid of me not to check the name of the person posting to
the list! Thanks for the nice paper by the way. :-)
I now see why heuristic gcd is inefficient for multivariable
polynomials. This seems to be a feature of multivariable algorithms. I
recently thought about using Kronecker substitution to multiply
multivariable polynomials and whilst it might work for 1 variable,
subsequent variables will make the integers too large for exactly the
reasons you give.
Do your timings you list include checking that the GCD is correct? Or
are the divisions still to be done?
According to the documentation on the Magma website:
"For polynomials over the integers or rationals, a combination of
three algorithms is used: (1) the heuristic evaluation `GCDHEU'
algorithm of Char et al. ([CGG89] and [GCL92, section 7.7]), suitable
for moderate-degree dense polynomials with several variables; (2) the
EEZ-GCD algorithm of Wang ([Wan80], [MY73] and [GCL92, section 7.6]),
based on evaluation and sparse ideal-adic multivariate Hensel lifting
([Wan78] and [GCL92, section 6.8]), suitable for sparse polynomials;
(3) a recursive multivariate evaluation-interpolation algorithm
(similar to that in [GCL92, section 7.4]), which in fact works
generically over {Z} or most fields."
I don't know any more than that.
The timings you give are very good. I can only compare with
polynomials in 1 variable. I think my timings are better than the ones
you give, but I won't be able to tell for sure until FLINT 1.1 is used
by Sage for GCD over ZZ (FLINT can't read from Sage python files). I'm
also only doing my timings on an Opteron. I don't know what they are
like on a Core 2.
Of course I used your paper in order to code the FLINT univariate GCD.
I cite it in the actual code, and as of 1 minute ago, it is liked from
the webpage of the FLINT project:
http://www.flintlib.org/
I'm currently doing some experiments with multivariable arithmetic in
FLINT. But I am only at the stage of adding polynomials. :-(
The method you suggest for doing the divisions sounds sensible to me.
Does that still take longer than the actual GCD?
Bill.
On 21 Jan, 21:00, parisse <bernard.pari...@ujf-grenoble.fr> wrote:
> Univariate polynomial GCD is very different from multivariate
> polynomial GCD.
> I know the heuristic gcd algorithm and the fact that for univariate
> polynomials, if you take z large enough (the bound is related to the
> resultant of the polynomials), you can not have a false positive,
> hence you don't need to check that the primitive part of the smod-
> reconstructed gcd divides both input (I suggest you to look at the
> author of the preprint you cited :-) ). But the bound is high, and it
> would be inefficient to use it, especially for polynomials with low
> gcd degree where modular gcd is much more efficient. In fact, giac
> univariate gcd algorithm first find the probable degree using a small
> modulo (that's a O(n^2) check where n is the degree of the
> polynomial), then decides which algorithm to use depending on the
> degree (modgcd for small degrees, heuristic gcd for intermediate and
> psr for degree almost equal to that of min(degree(input))).
> Heuristic gcd works also for multivariate polynomials but it is most
> of the time worse than modular, the reason being that you must use the
> same lower bound (2*min(|P|,|Q|)+2) for replacing a variable by an
> integer, and you must do it again on the new polynomial with 1 less
> variable + you must make the division checks (with sometimes failure)
> or use integers than are much too large. Even if all goes ok, at each
> step, the number of digits of the coefficients of the evaluated
> polynomial is multiplied by the partial degree, and you end up
> computing the gcd of 2 integers of that kind, which is O(number of
> digits^2) unless I'm mistaken, hence this step is approx O(product
> (partial degree^2)). For the modular algorithm, it is O
> (sum_degrees*product(partial degree)). That's most of the time much
> better, and that is the reason why I don't believe that one integer
> (multi-)evaluation can suceed proving divisibility faster for
> multivariate polynomial gcd.
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to
sage-devel-unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
