OK, I've looked into this more carefully and the reason why I don't know which is the best algorithm for polynomial gcd over Z is that most people when writing papers don't consider this case carefully when they come to do asymptotic or runtime analysis. That is presumably because it is hard to do so.
The best information I can find says that using classical multiplication methods, the runtime for the modular method is O(nm(n +m)) where n is the length of the polynomial and m is the number of bits per coefficient. The GCDHEU, EZGCD and EEZGCD methods only manage O(n^2m^2) with classical multiplication. For the subresultant method, an optimised version can complete the calculation in n^2M(m,m) + n^2M(2m,m) + n^2/2D(3m,2m) bit operations, where M(s,t) is the time to multiply an s bit and t bit integer and D(s,t) is the same thing but for division of two integers. As you can see it is not clear which of these strategies is subquadratic in n (if any), when fast multiplication techniques are used. Numerous strategies exist which are: the continued fraction method, Schoenhage's recursive half gcd, the fast euclidean algorithm, the accelerated euclidean algorithm, the binary recursive method, etc. But these only make sense if they are able to manage the coefficient explosion which happens over Z. Most of these other techniques really work best for gcd of integers or for polynomials over a finite field, where coefficient explosion doesn't occur. Which algorithm wins in practice probably depends on how well they are implemented. All of them seem to have been used by serious packages at one point or another, however it seems that the modular method almost always beats GCDHEU, EZGCD and EEZGCD if implemented well. In short, you are probably doing the best you can here. The only other possibility would be the subresultant method. I checked the source code for NTL and it uses a modular method to compute the resultant. Bill. --~--~---------~--~----~------------~-------~--~----~ 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/ -~----------~----~----~----~------~----~------~--~---
