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
-~----------~----~----~----~------~----~------~--~---
