The EEZ-GCD algorithm

ABSTRACT

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.

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: W. S. Brown, The Subresultant PRS Algorithm, ACM Transactions on Mathematical Software (TOMS), v.4 n.3, p.237-249, Sept. 1978 [doi>10.1145/355791.355795]
• 3: George E. Collins, Subresultants and Reduced Polynomial Remainder Sequences, Journal of the ACM (JACM), v.14 n.1, p.128-142, Jan. 1967 [doi>10.1145/321371.321381]
• 4: Hensel, K., <u>Zahlentheorie</u>, Goschen, Berlin and Leipzig, 1913.
• 5: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 6: Joel Moses , David Y. Y. Yun, The EZ GCD algorithm, Proceedings of the annual conference, p.159-166, August 27-29, 1973, Atlanta, Georgia, United States [doi>10.1145/800192.805698]
• 7: Wang, P. S. and Rothschild, L. P., "Factoring Multivariate Polynomials Over the Integers", Math. Comp., V. 29, 1975, pp. 935--950.
• 8: Wang, P. S., "Preserving Sparseness in Multivariate Polynomial Factorization", Proceedings, MACSYMA USERS' CONFERENCE, University of California at Berkeley, July 27--29, 1977.
• 9: Wang, P. S., "An Improved Multivariate Polynomial Factoring Algorithm", Mathematics of Computation, Vol. 32, Oct. 1978, pp. 1215--1231.
• 10: Wang, P. S., "Analysis of the p-adic Construction of Multivariate Correction Coefficients in Polynomial Factorization: Iteration vs. Recursion", Proceedings EUROSAM '79, June 26--28, 1979, Marseille, France.
• 11: Yun, D. Y. Y., "The Hensel Lemma in Algebraic Manipulation", Ph.D. Thesis, Department of Mathematics, MIT, Nov. 1973, (also Project MAC TR-138, Nov. 1974).
• 12: Zassenhaus, H., "On Hensel Factorization I", Journal of Number Theory, Vol. 1, 1969, pp. 291--311.
• 13: Richard Zippel, Probabilistic algorithms for sparse polynomials, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.216-226, June 01, 1979
• 14: MACSYMA Reference Manual, The Mathlab Group, LCS, M.I.T., Cambridge, Mass., May 1979.