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.