Algorithms for Polynomial GCD Computation over Algebraic Function Fields

Michael Monagan (CECM)

Monday, January 12, 2004, in K9509 at 3:30pm.

Let L be an algebraic function field in k parameters t1,t2,...,tk.
We present and compare two algorithms for computing the gcd of two
polynomials f1 and f2 in L[x].  The first algorithm is a modular
GCD algorithm.  It is an extension of the ideas of Brown for gcd
computation in Z[x1,...,xn] and Encarnacion for for gcd computation
in Q(alpha)[x].  The second algorithm is a fraction free algorithm.
It is a modification of the algorithm of Moreno-Maza and Rioboo
for gcd computation over triangular sets.  Our modification reduces
coefficient growth to be linear.  We give an empirical comparison
of Maple implementations of both algorithms.