
Algorithms for Polynomial GCD Computation over Algebraic Function FieldsMichael 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 MorenoMaza 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. 