The EZ GCD algorithm
Joel C. Moses, David Y. Y. Yun · ACM Annual Conference · 1973
This paper presents a preliminary report on a new algorithm for computing the Greatest Common Divisor (GCD) of two multivariate polynomials over the integers. The algorithm is strongly influenced by the method used for factoring multivariate polynomials over the integers. It uses an extension of the Hensel lemma approach originally suggested by Zassenhaus for factoring univariate polynomials over the integers. We point out that the cost of the Modular GCD algorithm applied to sparse multivariate polynomials grows at least exponentially in the number of variables appearing in the GCD. This growth is largely independent of the number of terms in the GCD. The new algorithm, called the EZ (Extended Zassenhaus) GCD Algorithm, appears to have a computing bound which in most cases is a polynomial function of the number of terms in the original polynomials and the sum of the degrees of the variables in them. Especially difficult cases for the EZ GCD Algorithm are described. Applications of the algorithm to the computation of contents and square-free decompositions of polynomials are indicated.
Cited by 74 works. doi:10.1145/800192.805698
Authors
References
- The Art of Computer Programming
- On Hensel factorization, I
- Factoring Polynomials Over Finite Fields
- Subresultants and Reduced Polynomial Remainder Sequences
- On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors
- On Euclid's Algorithm and the Theory of Subresultants
- The Calculation of Multivariate Polynomial Resultants
- Algorithms for polynomial factorization.
- The ALPAK System for Nonnumerical Algebra on a Digital Computer - II: Rational Functions of Several Variables and Truncated Power Series with Rational-Function Coefficients
- Towards a general theory of special functions