On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors

Full text

Pdf (1.56 MB)

Source

Journal of the ACM (JACM) archive
Volume 18 , Issue 4 (October 1971) table of contents

Pages: 478 - 504

Year of Publication: 1971

ISSN:0004-5411

Author

W. S. Brown

Bell Telephone Laboratories, Incorporated, Murray Hill, New Jersey

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 69, Citation Count: 67

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/321662.321664 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
	2	SAMMET J. E., ET AL. Symbol manipulation. Comm. ACM 9 (Aug. 65), 547-643.
	3	HOUSEHOLDER, A. S. Bigradients and the problem of Routh and Hurwitz, SIAM Rev. 10 (Jan. 1968), 56-66.
	4	HOUSEHOLDER, A. S., AND STEWART, G. W., I I I . Bigradients, Hankel determinants, and the Pads table. In Constructive Aspects of the Fundamental Theorem of Algebra, B. De- }on and P. Henrici, Eds. Wiley-Interscience, New York, 1969, pp. 131-150.
	5	USPENSKY, J.V. Theory of Equations, McGraw-Hill, New York, 1948.
	6	BIRKHOFF G., AND MACLANE, S. A Survey of Modern Algebra, 3rd ed. Macmillan, New York, 1965.
	7	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]
	8	W. S. Brown , J. F. Traub, On Euclid's Algorithm and the Theory of Subresultants, Journal of the ACM (JACM), v.18 n.4, p.505-514, Oct. 1971 [doi>10.1145/321662.321665]
	9	GOLDSTEIN A. J., AND GRAHAM, R.L. A Hadamard type bound on the coefficients of a determinant of analytic functions (to be published).
	10	George E. Collins, The calculation of multivariate polynomial resultants, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.212-222, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806289]
	11	ERD~LYI, A. Asymptotic Expansions. Dover, New York, 1956.
	12	Proc. 2nd Symposium on Symbolic and Algebraic Manipulation. ACM, New York, 1971, Chs. 3 and 7.

CITED BY 67

	R. T. Moenck, Fast computation of GCDs, Proceedings of the fifth annual ACM symposium on Theory of computing, p.142-151, April 30-May 02, 1973, Austin, Texas, United States
	B. F. Caviness , G. E. Collins, Symbolic mathematical computation in a Ph.D. computer science program, Proceedings of the second SIGCSE technical symposium on Education in computer science, p.19-23, March 01-01, 1972
	Michael T. McClellan, A Comparison of Algorithms for the Exact Solution of Linear Equations, ACM Transactions on Mathematical Software (TOMS), v.3 n.2, p.147-158, June 1977
	D. Castro , L. M. Pardo , J. San Martín, Systems of rational polynomial equations have polynomial size approximate zeros on the average, Journal of Complexity, v.19 n.2, p.161-209, April 2003
	S. Cabay , T. P. L. Lam, Congruence Techniques for the Exact Solution of Integer Systems of Linear Equations, ACM Transactions on Mathematical Software (TOMS), v.3 n.4, p.386-397, Dec. 1977
	B. F. Caviness , Michael Rothstein, A modular greatest common divisor algorithm for gaussian polynomials, Proceedings of the 1975 annual conference, p.270-273, January 1975
	Michael T. McClellan, The Exact Solution of Linear Equations with Rational Function Coefficients, ACM Transactions on Mathematical Software (TOMS), v.3 n.1, p.1-25, March 1977
	Wolfgang Küchlin, On the multi-threaded computation of integral polynomial greatest common divisors, Proceedings of the 1991 international symposium on Symbolic and algebraic computation, p.333-342, July 15-17, 1991, Bonn, West Germany
	David Y.Y. Yun, On square-free decomposition algorithms, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.26-35, August 10-12, 1976, Yorktown Heights, New York, United States
	W. S. Brown, On the subresultant PRS algorithm, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.271, August 10-12, 1976, Yorktown Heights, New York, United States
	W. S. Brown, The Subresultant PRS Algorithm, ACM Transactions on Mathematical Software (TOMS), v.4 n.3, p.237-249, Sept. 1978
	Paulina Chin , Robert M. Corless , George F. Corliss, Optimization strategies for the approximate GCD problem, Proceedings of the 1998 international symposium on Symbolic and algebraic computation, p.228-235, August 13-15, 1998, Rostock, Germany
	Lars Langemyr, An analysis of the subresultant algorithm over an algebraic number field, Proceedings of the 1991 international symposium on Symbolic and algebraic computation, p.167-172, July 15-17, 1991, Bonn, West Germany
	Isabelle Gil, Computation of the Jordan canonical form of a square matrix (using the Axiom programming language), Papers from the international symposium on Symbolic and algebraic computation, p.138-145, July 27-29, 1992, Berkeley, California, United States
	George E. Collins, The Calculation of Multivariate Polynomial Resultants, Journal of the ACM (JACM), v.18 n.4, p.515-532, Oct. 1971
	Hsin-Chao Liao , Richard J. Fateman, Evaluation of the heuristic polynomial GCD, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.240-247, July 10-12, 1995, Montreal, Quebec, Canada
	Anthony C. Hearn , Rüdiger G. K. Loos, Extended polynomial algorithms, Proceedings of the annual conference, p.147-152, August 27-29, 1973, Atlanta, Georgia, United States
	Ellis Horowitz, On the substitution of polynomial forms, Proceedings of the annual conference, p.153-158, August 27-29, 1973, Atlanta, Georgia, United States
	Erich Kaltofen , Michael B. Monagan, On the genericity of the modular polynomial GCD algorithm, Proceedings of the 1999 international symposium on Symbolic and algebraic computation, p.59-66, July 28-31, 1999, Vancouver, British Columbia, Canada
	E Kaltofen, Computing with polynomials given by straight-line programs I: greatest common divisors, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.131-142, May 06-08, 1985, Providence, Rhode Island, United States
	Angel Díaz , Erich Kaltofen, On computing greatest common divisors with polynomials given by black boxes for their evaluations, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.232-239, July 10-12, 1995, Montreal, Quebec, Canada
	David Y. Y. Yun, Algebraic algorithms using p-adic constructions, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.248-259, August 10-12, 1976, Yorktown Heights, New York, United States
	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
	Mohamed Omar Rayes , Paul S. Wang , Kenneth Weber, Parallelization of the sparse modular GCD algorithm for multivariate polynomials on shared memory multiprocessors, Proceedings of the international symposium on Symbolic and algebraic computation, p.66-73, July 20-22, 1994, Oxford, United Kingdom
	B. F. Caviness , R. J. Fateman, Simplification of radical expressions, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.329-338, August 10-12, 1976, Yorktown Heights, New York, United States
	Barry M. Trager , David Y.Y. Yun, Completing nth powers of polynomials, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.351-355, August 10-12, 1976, Yorktown Heights, New York, United States
	V. Strassen, The computational complexity of continued fractions, Proceedings of the fourth ACM symposium on Symbolic and algebraic computation, p.51-67, August 05-07, 1981, Snowbird, Utah, United States
	Daniel Reischert, Asymptotically fast computation of subresultants, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.233-240, July 21-23, 1997, Kihei, Maui, Hawaii, United States
	T. J. Smedley, A new modular algorithm for computation of algebraic number polynomial gcds, Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation, p.91-94, July 17-19, 1989, Portland, Oregon, United States
	Erich Kaltofen, Greatest common divisors of polynomials given by straight-line programs, Journal of the ACM (JACM), v.35 n.1, p.231-264, Jan. 1988
	Michael B. Monagan , Allan D. Wittkopf, On the design and implementation of Brown's algorithm over the integers and number fields, Proceedings of the 2000 international symposium on Symbolic and algebraic computation, p.225-233, July 2000, St. Andrews, Scotland
	Ziming Li , István Nemes, A modular algorithm for computing greatest common right divisors of Ore polynomials, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.282-289, July 21-23, 1997, Kihei, Maui, Hawaii, United States
	Joachim von zur Gathen , Thomas Lücking, Subresultants revisited, Theoretical Computer Science, v.297 n.1-3, p.199-239, 17 March 2003
	E. Kaltofen , Y. N. Lakshman , J.-M. Wiley, Modular rational sparse multivariate polynomial interpolation, Proceedings of the international symposium on Symbolic and algebraic computation, p.135-139, August 20-24, 1990, Tokyo, Japan
	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
	Anthony C. Hearn, An improved non-modular polynomial GCD algorithm, ACM SIGSAM Bulletin
	B. F. Caviness , G. E. Collins, Symbolic mathematical computation in a Ph. D. computer science program, ACM SIGCSE Bulletin, v.4 n.1, March 1972
	Alfonso Miola , David Y. Y. Yun, Computational aspects of Hensel-type univariate polynomial greatest common divisor algorithms, ACM SIGSAM Bulletin, v.8 n.3, p.46-54, August 1974
	Shuhong Gao , Alan G. B. Lauder, Hensel lifting and bivariate polynomial factorisation over finite fields, Mathematics of Computation, v.71 n.240, p.1663-1676, October 2002
	G. L. Ebert, Some comments on the modular approach to Gröbner-bases, ACM SIGSAM Bulletin, v.17 n.2, p.28-32, May 1983
	S. C. Johnson, A note on abnormal polynomial remainder sequences, ACM SIGSAM Bulletin, v.9 n.3, p.28-29, August 1975
	Brent Gregory , Erich Kaltofen, Analysis of the binary complexity of asymptotically fast algorithms for linear system solving, ACM SIGSAM Bulletin, v.22 n.2, p.41-49, April 1988
	Alain Lascoux , Piotr Pragacz, Double Sylvester sums for subresultants and multi-Schur functions, Journal of Symbolic Computation, v.35 n.6, p.689-710, June 2003
	W. Morven Gentleman, On computing certain integrals, and implications for symbolic algebraic manipulation, Proceedings of the ACM annual conference, p.840-843, August 01-01, 1972, Boston, Massachusetts, United States
	Juan R. Sendra , Juan Llovet, Efficient algorithms for Hankel matrices over Z[x1,…,xr], Proceedings of the 1993 international symposium on Symbolic and algebraic computation, p.201-208, July 06-08, 1993, Kiev, Ukraine
	Shuhong Gao, Factoring multivariate polynomials via partial differential equations, Mathematics of Computation, v.72 n.242, p.801-822, 1 April 2003
	David Y. Y. Yun, A p-adic division with remainder algorithm, ACM SIGSAM Bulletin, v.8 n.4, p.27-32, November 1974
	Juan R. Sendra, Hankel matrices and computer algebra, ACM SIGSAM Bulletin, v.24 n.3, p.17-26, Jul. 1990
	Zhonggang Zeng , Barry H. Dayton, The approximate GCD of inexact polynomials, Proceedings of the 2004 international symposium on Symbolic and algebraic computation, p.320-327, July 04-07, 2004, Santander, Spain
	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
	Joachim von zur Gathen, Parallel algorithms for algebraic problems, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.17-23, December 1983
	George E. Collins, Quantifier elimination for real closed fields by cylindrical algebraic decomposition--preliminary report, ACM SIGSAM Bulletin, v.8 n.3, p.80-90, August 1974
	James H. Griesmer, Symbolic mathematical computation: a survey, ACM SIGSAM Bulletin, v.10 n.2, p.30-32, May 1976
	David Y. Y. Yun, On algorithms for solving systems of polynomial equations, ACM SIGSAM Bulletin
	W. S. Brown, On computing with factored rational expressions, ACM SIGSAM Bulletin, v.8 n.3, p.26-34, August 1974
	Joel Moses, MACSYMA - the fifth year, ACM SIGSAM Bulletin, v.8 n.3, p.105-110, August 1974
	Richard D. Jenks, Course outline: Yale University, New Haven, ACM SIGSAM Bulletin, v.9 n.3, p.9-10, August 1975
	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
	Rüdiger Loos, Algebraic algorithm descriptions as programs, ACM SIGSAM Bulletin
	Paul S. Wang, The EEZ-GCD algorithm, ACM SIGSAM Bulletin, v.14 n.2, p.50-60, May 1980
	Stuart I. Feldman, A brief description of Altran, ACM SIGSAM Bulletin, v.9 n.4, p.12-20, November 1975
	Paul S. Wang , L. Preiss Rothschild, Factoring multivariate polynomials over the integers, ACM SIGSAM Bulletin
	Howard Cheng , George Labahn, Output-sensitive modular algorithms for polynomial matrix normal forms, Journal of Symbolic Computation, v.42 n.7, p.733-750, July, 2007
	Howard Cheng , George Labahn, On computing polynomial GCDs in alternate bases, Proceedings of the 2006 international symposium on Symbolic and algebraic computation, July 09-12, 2006, Genoa, Italy
	Seyed Mohammad Mahdi Javadi , Michael Monagan, A sparse modular GCD algorithm for polynomials over algebraic function fields, Proceedings of the 2007 international symposium on Symbolic and algebraic computation, July 29-August 01, 2007, Waterloo, Ontario, Canada
	Guillaume Chèze , Jean-Claude Yakoubsohn , André Galligo , Bernard Mourrain, Computing nearest Gcd with certification, Proceedings of the 2009 conference on Symbolic numeric computation, August 03-05, 2009, Kyoto, Japan
	Xiaolin Qin , Yong Feng , Jingwei Chen , Jingzhong Zhang, Finding exact minimal polynomial by approximations, Proceedings of the 2009 conference on Symbolic numeric computation, August 03-05, 2009, Kyoto, Japan