A sparse modular GCD algorithm for polynomials over algebraic function fields

ABSTRACT

We present a first sparse modular algorithm for computing a greatest common divisor of two polynomials f₁, f₂ ε L[x] where L is an algebraic function field in k ≥ 0 parameters with r ≥ 0 field extensions. Our algorithm extends the dense algorithm of Monagan and van Hoeij from 2004 to support multiple field extensions and to be efficient when the gcd is sparse. Our algorithm is an output sensitive Las Vegas algorithm.

We have implemented our algorithm in Maple. We provide timings demonstrating the efficiency of our algorithm compared to that of Monagan and van Hoeij and with a primitive fraction-free Euclidean algorithm for both dense and sparse gcd problems.

REFERENCES

• 1: W. S. Brown, On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors, Journal of the ACM (JACM), v.18 n.4, p.478-504, Oct. 1971 [doi>10.1145/321662.321664]
• 2: Xavier Dahan , Marc Moreno Maza , Eric Schost , Wenyuan Wu , Yuzhen Xie, Lifting techniques for triangular decompositions, Proceedings of the 2005 international symposium on Symbolic and algebraic computation, p.108-115, July 24-27, 2005, Beijing, China [doi>10.1145/1073884.1073901]
• 3: Mark van Hoeij , Michael Monagan, A modular GCD algorithm over number fields presented with multiple extensions, Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.109-116, July 07-10, 2002, Lille, France [doi>10.1145/780506.780520]
• 4: Mark van Hoeij , Michael Monagan, Algorithms for polynomial GCD computation over algebraic function fields, Proceedings of the 2004 international symposium on Symbolic and algebraic computation, p.297-304, July 04-07, 2004, Santander, Spain [doi>10.1145/1005285.1005328]
• 5: Sara Khodadad , Michael Monagan, Fast rational function reconstruction, Proceedings of the 2006 international symposium on Symbolic and algebraic computation, July 09-12, 2006, Genoa, Italy [doi>10.1145/1145768.1145801]
• 6: Jennifer de Kleine , Michael Monagan , Allan Wittkopf, Algorithms for the non-monic case of the sparse modular GCD algorithm, Proceedings of the 2005 international symposium on Symbolic and algebraic computation, p.124-131, July 24-27, 2005, Beijing, China [doi>10.1145/1073884.1073903]
• 7: Marc Moreno Maza , Renaud Rioboo, Polynomial Gcd Computations over Towers of Algebraic Extensions, Proceedings of the 11th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.365-382, July 17-22, 1995
• 8: Michael Monagan, Maximal quotient rational reconstruction: an almost optimal algorithm for rational reconstruction, Proceedings of the 2004 international symposium on Symbolic and algebraic computation, p.243-249, July 04-07, 2004, Santander, Spain [doi>10.1145/1005285.1005321]
• 9: Paul S. Wang, Early detection of true factors in univariate polynominal factorization, Proceedings of the European Computer Algebra Conference on Computer Algebra, p.225-235, March 28-30, 1983
• 10: Richard Zippel, Probabilistic algorithms for sparse polynomials, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.216-226, June 01, 1979

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

General Terms:
Algorithms, Theory

Keywords:
GCD algorithms, algebraic function fields, sparse interpolation