The Calculation of Multivariate Polynomial Resultants

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The Calculation of Multivariate Polynomial Resultants

Full text

Pdf (1.10 MB)

Source

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

Pages: 515 - 532

Year of Publication: 1971

ISSN:0004-5411

Author

George E. Collins

University of Wisconsin, Computer Sciences Department, Madison, Wisconsin

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 39, Citation Count: 38

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.321666 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	S. Gorn, FORTRAN vs. Basic FORTRAN: a programming language for informational processing on automatic data processing systems, Communications of the ACM, v.7 n.10, p.591-624, Oct. 1964 [doi>10.1145/364888.876694]
	2	BODEWIG, E. Matrix Calculus. North Holland, Amsterdam, 1959.
	3	DROWN, W. S. The Compleat Euclidean Algorithm. Bell Telephone Laboratories Rep., Murray Hill, N. J., June 1968.
	4	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]
	5	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]
	6	BUTCHER, J. C. On Runge-Kutta processes of high order. J. Australian Math. Soe. 4 (1964), 179-194.
	7	CESCHINO, F. AND KUNTZMANN, J. Numerical Solution of Initial Value Problems. Prentice-Hull, Englewood Cliffs, N. J., 1966, pp. 72-74.
	8	G. E. Collins, PM, a system for polynomial manipulation, Communications of the ACM, v.9 n.8, p.578-589, Aug. 1966 [doi>10.1145/365758.365770]
	9	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]
	10	COLLINS, G. E. The SAC-1 polynomial system. U. of Wisconsin Computing Center Tech. Rep. No. 2, U. of Wisconsin, Madison, Wis., March 1968.
	11	COLLINS, G. E., HEINDEL, L. E., HOROWITZ, E., McCLELLAN, M. T. AND MUSSER, D. R. The SAC-1 modular arithmetic system. U. of Wisconsin Technical Report No. 10, U. of Wisconsin, Wis., June 1969.
	12	George E. Collins, Letters to the editor: comment on a paper by Ku and Adler, Communications of the ACM, v.12 n.6, p.302-303, June 1969 [doi>10.1145/363011.363017]
	13	COLLINS, G. E. The SAC-1 polynomial G.C.D. and resultant system. (In preparation.)
	14	George E. Collins, The SAC-1 system: An introduction and survey, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.144-152, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806279]
	15	Lee E. Heindel, Integer arithmetic algorithms for polynomial real zero determination, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.415-426, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806312]
	16	JACOBSON, N. Lectures in Abstract Algebra, Vol. HI: Theory of Fields and Galois Theory. Van Nostrand, Princeton, N. J., 1964.
	17	Donald E. Knuth, The Art of Computer Programming Volumes 1-3 Boxed Set, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
	18	Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
	19	Ku, S. Y., AND ADLER, R.J. Algebra-based methods for solving multivariate polynomial equations. Chemical Eng. Sci. Division Rep. No. 10-22--68. Case Western Reserve U., 1968.
	20	S. Y. Ku , R. J. Adler, Computing polynomial resultants: Bezout's determinant vs. Collins' reduced P.R.S. algorithm, Communications of the ACM, v.12 n.1, p.23-30, Jan. 1969 [doi>10.1145/362835.362839]
	21	Michael T. McClellan, The exact solution of systems of linear equations with polynomial coefficients, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.399-414, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806311]
	22	Joel Moses, Solutions of systems of polynomial equations by elimination, Communications of the ACM, v.9 n.8, p.634-637, Aug. 1966 [doi>10.1145/365758.365802]
	23	David Rea Musser, Algorithms for polynomial factorization., 1971
	24	TAKAHASI, H., AND ISHIDASHI, Y. A new method for exact calculation by computer, Inform. Proces. Japan 1 (1961), 28-42.
	25	TARSm, A. A Decision Method for Elementary Algebra and Geometry. U. of California Press, 1951.
	26	VAN DER WAERDEN, B.L. Modern Algebra, Vol. I. Ungar, New York, 1948.
	27	VAN DER WAERDEN, B.L. Modern Algebra, Vol. ~. Ungar, New York, 1950.

CITED BY 38

	Barry M. Trager, Algebraic factoring and rational function integration, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.219-226, August 10-12, 1976, Yorktown Heights, New York, United States
	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
	Muhammed I. Syam, Finding all real zeros of polynomial systems using multi-resultant, Journal of Computational and Applied Mathematics, v.167 n.2, p.417-428, 1 June 2004
	Markus Lauer, A solution to Kahan's problem (SIGSAM problem no. 9), ACM SIGSAM Bulletin, v.11 n.2, p.16-20, May 1977
	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
	Juan R. Sendra, Hankel matrices and computer algebra, ACM SIGSAM Bulletin, v.24 n.3, p.17-26, Jul. 1990
	Richard D. Jenks, Problem #11: generation of Runge-Kutta equations, ACM SIGSAM Bulletin, v.10 n.1, p.6-7, February 1976
	B. F. Caviness , G. E. Collins, Algorithms for Gaussian integer arithmetic, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.36-45, August 10-12, 1976, Yorktown Heights, New York, 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
	Manuel Bronstein, Gsolve: a faster algorithm for solving systems of algebraic equations, Proceedings of the fifth ACM symposium on Symbolic and algebraic computation, p.247-249, July 21-23, 1986, Waterloo, Ontario, Canada
	Dennis Weeks, Formal representations for algebraic numbers, ACM SIGSAM Bulletin, v.8 n.3, p.91-95, August 1974
	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
	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
	J. T. Schwartz, Fast Probabilistic Algorithms for Verification of Polynomial Identities, Journal of the ACM (JACM), v.27 n.4, p.701-717, Oct. 1980
	James R. Pinkert, An Exact Method for Finding the Roots of a Complex Polynomial, ACM Transactions on Mathematical Software (TOMS), v.2 n.4, p.351-363, Dec. 1976
	Mark J. Encarnación, Factoring polynomials over algebraic number fields via norms, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.265-270, July 21-23, 1997, Kihei, Maui, Hawaii, 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
	Eng-Wee Chionh , Ronald N. Goldman , James R. Miller, Using multivariate resultants to find the intersection of three quadric surfaces, ACM Transactions on Graphics (TOG), v.10 n.4, p.378-400, Oct. 1991
	Scott McCallum , George E. Collins, Local box adjacency algorithms for cylindrical algebraic decompositions, Journal of Symbolic Computation, v.33 n.3, p.321-342, March 2002
	Joel Moses, MACSYMA - the fifth year, ACM SIGSAM Bulletin, v.8 n.3, p.105-110, August 1974
	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
	David Y. Y. Yun, On algorithms for solving systems of polynomial equations, ACM SIGSAM Bulletin
	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
	Webb Miller, Toward mechanical verification of properties of roundoff error propagation, Proceedings of the fifth annual ACM symposium on Theory of computing, p.50-58, April 30-May 02, 1973, Austin, Texas, United States
	Wolfgang Schreiner , Christian Mittermaier , Karoly Bosa, Distributed maple: parallel computer algebra in networked environments, Journal of Symbolic Computation, v.35 n.3, p.305-347, March 2003
	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
	Joachim von zur Gathen , Thomas Lücking, Subresultants revisited, Theoretical Computer Science, v.297 n.1-3, p.199-239, 17 March 2003
	Deepak Kapur , Tushar Saxena, Comparison of various multivariate resultant formulations, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.187-194, July 10-12, 1995, Montreal, Quebec, Canada
	Joachim von zur Gathen , Silke Hartlieb, Factoring modular polynomials (extended abstract), Proceedings of the 1996 international symposium on Symbolic and algebraic computation, p.10-17, July 24-26, 1996, Zurich, Switzerland
	S. S. Abhyankar , C. J. Bajaj, Automatic parameterization of rational curves and surfaces IV: algebraic space curves, ACM Transactions on Graphics (TOG), v.8 n.4, p.325-334, Oct. 1989
	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
	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
	C. Bajaj , M. Kim, Compliant motion planning with geometric models, Proceedings of the third annual symposium on Computational geometry, p.171-180, June 08-10, 1987, Waterloo, Ontario, Canada
	Michael T. McClellan, The Exact Solution of Systems of Linear Equations with Polynomial Coefficients, Journal of the ACM (JACM), v.20 n.4, p.563-588, Oct. 1973
	L. W. Ericson , C. K. Yap, The design of LINETOOL, a geometric editor, Proceedings of the fourth annual symposium on Computational geometry, p.83-92, June 06-08, 1988, Urbana-Champaign, Illinois, United States
	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
	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
	Chionh Eng Wee , Ronald N. Goldman, Elimination and Resultants - Part 1: Elimination and Bivariate Resultants, IEEE Computer Graphics and Applications, v.15 n.1, p.69-77, January 1995