More Web Proxy on the site http://driver.im/

Article

Free access

The EZ GCD algorithm

Authors:

David Y. Y. YunAuthors Info & Claims

ACM '73: Proceedings of the ACM annual conference

Pages 159 - 166

https://doi.org/10.1145/800192.805698

Published: 27 August 1973 Publication History

Abstract

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.

References

[1]

Berlekamp, E. R., "Factoring Polynomials over Finite Fields", Bell System Technical Journal, Vol. 46, 1967, MR #2314, pp. 1853-1859.

[2]

Bonneau, R., "The Fast Fourier Transform and Polynomial Multiplications", Department of Mathematics, M.I.T. (in preparation).

[3]

Brown, W. S., "On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors", JACM, Vol. 18, No. 4, October, 1971, pp. 478-504.

Digital Library

[4]

Brown, W. S., Hyde, J. P., and Tague, B. A., "The ALPAK System for Numerical Algebra on a Digital Computer - II", The Bell System Technical Journal, March, 1964, pp. 785-804.

[5]

Brown, W. S., and Traub, J. F., "On Euclid's Algorithm and the Theory of Subresultants", JACM, Vol. 18, No. 4, October, 1971, pp. 504-518.

Digital Library

[6]

Collins, G. E., "Subresultants and Reduced Polynomial Remainder Sequences", JACM, Vol. 14, January, 1967, pp. 128-142.

Digital Library

[7]

Collins, G. E., "The Calculation of Multivariate Polynomial Resultants", JACM, Vol. 18, No. 4, October, 1971, pp. 515-532.

Digital Library

[8]

Fateman, R. J., "On the Computation of Powers of Polynomials", Department of Mathematics, M.I.T. (unpublished).

[9]

Knuth, D. E., The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, Addison Wesley, Reading, Massachusetts 1969.

Digital Library

[10]

MACSYMA User's Manual, by Bogen, R., et al., Project MAC, M.I.T., Cambridge, Mass., 1973.

[11]

Moses, J., "Towards a General Theory of Special Functions", Communications of ACM, Vol. 15, No. 7, July, 1972.

Digital Library

[12]

Musser, D. R., "Algorithms for Polynomial Factorization", Ph.D. Thesis, Computer Science Department, University of Wisconsin, August, 1971.

Digital Library

[13]

Proc. of the Second Symposium on Symbolic and Algebraic Manipulation, Petrick, S. R., ed., ACM, March, 1971.

[14]

Van der Waerden, B. L., Modern Algebra, Vol. 1, Frederic Ungar Publishing Co., N.Y., 1953.

[15]

Wang, P. S., and Rothschild, L. P., "Factoring Multivariate Polynomials over the Integers", (submitted to Mathematics of Computation).

[16]

Yun, D. Y. Y., "The Hensel Lemma in GCD Calculations", Department of Mathematics, M.I.T., (in preparation).

[17]

Zassenhaus, H., "On Hensel Factorization I", Journal of Number Theory, Vol. 1, 1969, pp. 291-311.

Cited By

Nagasaka K(2025)Approximate GCD of several multivariate sparse polynomials based on SLRA interpolationJournal of Symbolic Computation10.1016/j.jsc.2024.102368127:COnline publication date: 1-Mar-2025
https://dl.acm.org/doi/10.1016/j.jsc.2024.102368
Monagan MHuang Q(2024)A New Sparse Polynomial GCD by Separating TermsProceedings of the 2024 International Symposium on Symbolic and Algebraic Computation10.1145/3666000.3669684(134-142)Online publication date: 16-Jul-2024
https://dl.acm.org/doi/10.1145/3666000.3669684
Nagasaka K(2023)SLRA Interpolation for Approximate GCD of Several Multivariate PolynomialsProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597116(470-479)Online publication date: 24-Jul-2023
https://dl.acm.org/doi/10.1145/3597066.3597116
Show More Cited By

Index Terms

The EZ GCD algorithm
1. Computing methodologies
  1. Symbolic and algebraic manipulation
2. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Computation of transforms
      2. Number-theoretic computations

Recommendations

The EEZ-GCD algorithm

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 ...
Improvement of EZ-GCD algorithm based on extended hensel construction

In [2], we proposed the EZ-GCD algorithm based on extended Hensel construction, in order to compute the GCD of multivariate polynomials. The extended Hensel construction is a specify factorization into algebraic function, and it is efficient for sparse ...
Approximate polynomial GCD over integers

Symbolic numeric algorithms for polynomials are very important, especially for practical computations since we have to operate with empirical polynomials having numerical errors on their coefficients. Recently, for those polynomials, a number of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ACM '73: Proceedings of the ACM annual conference

August 1973

472 pages

ISBN:9781450374903

DOI:10.1145/800192

Copyright © 1973 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

ACM: Association for Computing Machinery

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 August 1973

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

52
Total Citations
View Citations
330
Total Downloads

Downloads (Last 12 months)136
Downloads (Last 6 weeks)20

Reflects downloads up to 09 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Nagasaka K(2025)Approximate GCD of several multivariate sparse polynomials based on SLRA interpolationJournal of Symbolic Computation10.1016/j.jsc.2024.102368127:COnline publication date: 1-Mar-2025
https://dl.acm.org/doi/10.1016/j.jsc.2024.102368
Monagan MHuang Q(2024)A New Sparse Polynomial GCD by Separating TermsProceedings of the 2024 International Symposium on Symbolic and Algebraic Computation10.1145/3666000.3669684(134-142)Online publication date: 16-Jul-2024
https://dl.acm.org/doi/10.1145/3666000.3669684
Nagasaka K(2023)SLRA Interpolation for Approximate GCD of Several Multivariate PolynomialsProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597116(470-479)Online publication date: 24-Jul-2023
https://dl.acm.org/doi/10.1145/3597066.3597116
Wang DWang HWei JXiao F(2023)An extended GCRD algorithm for parametric univariate polynomial matrices and application to parametric Smith formJournal of Symbolic Computation10.1016/j.jsc.2022.07.006115(248-265)Online publication date: Mar-2023
https://doi.org/10.1016/j.jsc.2022.07.006
Monagan MPaluck GMaza MZhi L(2022)Linear Hensel Lifting for Zp[x,y] for n Factors with Cubic CostProceedings of the 2022 International Symposium on Symbolic and Algebraic Computation10.1145/3476446.3536178(159-166)Online publication date: 4-Jul-2022
https://dl.acm.org/doi/10.1145/3476446.3536178
Hu JMonagan M(2020)A fast parallel sparse polynomial GCD algorithmJournal of Symbolic Computation10.1016/j.jsc.2020.06.001Online publication date: Jun-2020
https://doi.org/10.1016/j.jsc.2020.06.001
Sanuki M(2019)Improvement of EZ-GCD algorithm based on extended hensel constructionACM Communications in Computer Algebra10.1145/3338637.333864952:4(148-150)Online publication date: 30-May-2019
https://dl.acm.org/doi/10.1145/3338637.3338649
Monagan MDavenport JWang DKauers MBradford R(2019)Linear Hensel Lifting for Fp[x,y] and Z[x] with Cubic CostProceedings of the 2019 International Symposium on Symbolic and Algebraic Computation10.1145/3326229.3326242(299-306)Online publication date: 8-Jul-2019
https://dl.acm.org/doi/10.1145/3326229.3326242
Kapur DLu DMonagan MSun YWang DKauers MOvchinnikov ASchost É(2018)An Efficient Algorithm for Computing Parametric Multivariate Polynomial GCDProceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation10.1145/3208976.3208980(239-246)Online publication date: 11-Jul-2018
https://dl.acm.org/doi/10.1145/3208976.3208980
Alvandi PAtaei MMoreno Maza MYap CEl Din M(2017)On the Extended Hensel Construction and its Application to the Computation of Limit PointsProceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation10.1145/3087604.3087658(13-20)Online publication date: 23-Jul-2017
https://dl.acm.org/doi/10.1145/3087604.3087658
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten