On Euclid's Algorithm and the Theory of Subresultants

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On Euclid's Algorithm and the Theory of Subresultants

Full text

Pdf (457 KB)

Source

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

Pages: 505 - 514

Year of Publication: 1971

ISSN:0004-5411

Authors

W. S. Brown	Bell Telephone Laboratories, Incorporated Murray Hill, New Jersey
J. F. Traub	Carnegie-Mellon University, Department of Computer Science, Pittsburgh, Pennsylvania

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 57, Citation Count: 48

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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.321665 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	W. S. Brown, On Euclid's algorithm and the computation of polynomial greatest common divisors, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.195-211, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806288]
	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	BIRKHOFF, G., AND MACLANE, S. A Survey of Modern Algebra, 3rd ed. Macmillan, New York, 1965.
	5	USPENSKY, J.V. Theory of Equations. McGraw-Hill, New York, 1948.
	6	BOCHEa, M. Introduction to Higher Algebra. Macmillan, New York, 1907.
	7	HOUSEHOLDER, A.S. Bigradients and the problem of Routh and Hurwitz. SIAM Rev. 10 (1968), 56--66.
	8	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]
	9	Lee Edward Heindel, Algorithms for exact polynomial root calculation, 1971

CITED BY 48

	Michael Monagan, Probabilistic algorithms for computing resultants, Proceedings of the 2005 international symposium on Symbolic and algebraic computation, p.245-252, July 24-27, 2005, Beijing, China
	Tateaki Sasaki, The subresultant and clusters of close roots, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.232-239, August 03-06, 2003, Philadelphia, PA, USA
	M'hammed El Kahoui, An elementary approach to subresultants theory, Journal of Symbolic Computation, v.35 n.3, p.281-292, March 2003
	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
	Kuniaki Tsuji, An improved EZ-GCD algorithm for multivariate polynomials, Journal of Symbolic Computation, v.44 n.1, p.99-110, January, 2009
	Erich Kaltofen , Wen-shin Lee , Austin A. Lobo, Early termination in Ben-Or/Tiwari sparse interpolation and a hybrid of Zippel's algorithm, Proceedings of the 2000 international symposium on Symbolic and algebraic computation, p.192-201, July 2000, St. Andrews, Scotland
	Mark Giesbrecht , Erich Kaltofen , Wen-shin Lee, Algorithms for computing the sparsest shifts of polynomials via the Berlekamp/Massey algorithm, Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.101-108, July 07-10, 2002, Lille, France
	John Canny, Some algebraic and geometric computations in PSPACE, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.460-469, May 02-04, 1988, Chicago, Illinois, United States
	S. C. Johnson, A note on abnormal polynomial remainder sequences, ACM SIGSAM Bulletin, v.9 n.3, p.28-29, August 1975
	Jiawang Nie , James Demmel , Ming Gu, Global minimization of rational functions and the nearest GCDs, Journal of Global Optimization, v.40 n.4, p.697-718, April 2008
	W. S. Brown, The Subresultant PRS Algorithm, ACM Transactions on Mathematical Software (TOMS), v.4 n.3, p.237-249, Sept. 1978
	Nicola Geismann , Michael Hemmer , Elmar Schömer, Computing a 3-dimensional cell in an arrangement of quadrics: exactly and actually!, Proceedings of the seventeenth annual symposium on Computational geometry, p.264-273, June 2001, Medford, Massachusetts, United States
	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
	Tim Culver , John Keyser , Dinesh Manocha, Exact computation of the medial axis of a polyhedron, Computer Aided Geometric Design, v.21 n.1, p.65-98, January 2004
	Y. N. Lakshman, On the complexity of computing a Gröbner basis for the radical of a zero dimensional ideal, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.555-563, May 13-17, 1990, Baltimore, Maryland, United States
	Carlos DAndrea , Hoon Hong , Teresa Krick , Agnes Szanto, An elementary proof of Sylvester's double sums for subresultants, Journal of Symbolic Computation, v.42 n.3, p.290-297, March, 2007
	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
	Michael Ben-Or , Dexter Kozen , John Reif, The complexity of elementary algebra and geometry, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.457-464, December 1984
	E. Kaltofen , A. Lobo, On rank properties of Toeplitz matrices over finite fields, Proceedings of the 1996 international symposium on Symbolic and algebraic computation, p.241-249, July 24-26, 1996, Zurich, Switzerland
	Anthony C. Hearn, An improved non-modular polynomial GCD algorithm, ACM SIGSAM Bulletin
	E. Kaltofen, Single-factor Hensel lifting and its application to the straight-line complexity of certain polynomials, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.443-452, January 1987, New York, New York, United States
	Wen-shin Lee, From quotient-difference to generalized eigenvalues and sparse polynomial interpolation, Proceedings of the 2007 international workshop on Symbolic-numeric computation, July 25-27, 2007, London, Ontario, Canada
	Luca Gemignani, GCD of polynomials and Bezout matrices, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.271-277, July 21-23, 1997, Kihei, Maui, Hawaii, United States
	Ziming Li, A subresultant theory for Ore polynomials with applications, Proceedings of the 1998 international symposium on Symbolic and algebraic computation, p.132-139, August 13-15, 1998, Rostock, Germany
	David Y. Y. Yun, On algorithms for solving systems of polynomial equations, ACM SIGSAM Bulletin
	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
	D. Bini , L. Gemignani, On the Euclidean scheme for polynomials having interlaced real zeros, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.254-258, July 02-06, 1990, Island of Crete, Greece
	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
	D. A. Bini , L. Gemignani, Bernstein-Bezoutian matrices, Theoretical Computer Science, v.315 n.2-3, p.319-333, 6 May 2004
	George E. Collins, The Calculation of Multivariate Polynomial Resultants, Journal of the ACM (JACM), v.18 n.4, p.515-532, Oct. 1971
	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
	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
	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
	Joachim von zur Gathen , Thomas Lücking, Subresultants revisited, Theoretical Computer Science, v.297 n.1-3, p.199-239, 17 March 2003
	J. F. Canny , E. Kaltofen , L. Yagati, Solving systems of nonlinear polynomial equations faster, Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation, p.121-128, July 17-19, 1989, Portland, Oregon, United States
	Bernhard Beckermann , Stan Cabay , George Labahn, Fraction-free computation of matrix Padé systems, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.125-132, July 21-23, 1997, Kihei, Maui, Hawaii, United States
	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
	N. Karmarkar , Y. N. Lakshman, Approximate polynomial greatest common divisors and nearest singular polynomials, Proceedings of the 1996 international symposium on Symbolic and algebraic computation, p.35-39, July 24-26, 1996, Zurich, Switzerland
	Tim Culver , John Keyser , Dinesh Manocha, Accurate computation of the medial axis of a polyhedron, Proceedings of the fifth ACM symposium on Solid modeling and applications, p.179-190, June 08-11, 1999, Ann Arbor, Michigan, United States
	Bernhard Beckermann , Howard Cheng , George Labahn, Fraction-free row reduction of matrices of skew polynomials, Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.8-15, July 07-10, 2002, Lille, France
	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
	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
	John H. Reif, Work efficient parallel solution of Toeplitz systems and polynomial GCD, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.751-761, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Elmar Schömer , Nicola Wolpert, An exact and efficient approach for computing a cell in an arrangement of quadrics, Computational Geometry: Theory and Applications, v.33 n.1-2, p.65-97, January 2006
	John H. Reif, Efficient parallel factorization and solution of structured and unstructured linear systems, Journal of Computer and System Sciences, v.71 n.1, p.86-143, July 2005
	Arno Eigenwillig , Lutz Kettner , Elmar Schömer , Nicola Wolpert, Exact, efficient, and complete arrangement computation for cubic curves, Computational Geometry: Theory and Applications, v.35 n.1, p.36-73, August 2006
	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
	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