The EEZ-GCD algorithm
Paul S. Wang · ACM SIGSAM Bulletin · 1980
An enhanced gcd algorithm based on the EZ-GCD algorithm is described. Implementational aspects are emphasized. It is generally faster and is particularly suited for computing gcd of sparse multivariate polynomials. The EEZ-GCD algorithm is characterized by the following features:(1) avoiding unlucky evaluations,(2) predetermining the correct leading coefficient of the desired gcd,(3) using the sparsity of the given polynomials to determine terms in the gcd and(4) direct methods for dealing with the "common divisor problem." The common divisor problem occurs when the gcd has a different common divisor with each of the cofactors. The EZ-GCD algorithm does a square-free decomposition in this case. It can be avoided resulting in increased speed. One method is to use parallel p-adic construction of more than two factors. Machine examples with timing data are included.
Cited by 39 works. doi:10.1145/1089220.1089228
Authors
References
- The Art of Computer Programming
- On Hensel factorization, I
- Probabilistic algorithms for sparse polynomials
- Subresultants and Reduced Polynomial Remainder Sequences
- On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors
- The Hensel lemma in algebraic manipulation
- An Improved Multivariate Polynomial Factoring Algorithm
- Factoring multivariate polynomials over the integers
- The EZ GCD algorithm
- The Subresultant PRS Algorithm