Polynomial real root isolation by differentiation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Polynomial real root isolation by differentiation

Full text

Pdf (855 KB)

Source

Symposium on Symbolic and Algebraic Manipulation archive
Proceedings of the third ACM symposium on Symbolic and algebraic computation table of contents

Yorktown Heights, New York, United States

Pages: 15 - 25

Year of Publication: 1976

Authors

George E. Collins
Rüdiger Loos

Sponsors

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation
SYMSAC : SYMSAC

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 46, Citation Count: 13

Additional Information:

abstract 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/800205.806319 What is a DOI?

ABSTRACT

A new algorithm is described, for the isolation of the real roots of a real polynomial. This algorithm utilizes the sequence of derivatives of the given polynomial, relying on Rolle's theorem and a tangent construction to decide whether an interval contains two roots or none. The algorithm is carefully compared, both analytically and empirically, with an algorithm based on Sturm's theorem, and is found to be significantly faster in general. It also requires less memory, and produces isolating intervals for the derivatives as a cost-free by-product.

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	Collins, G.E., The SAC-1 Integer Arithmetic System—Version III, Technical Report WIS-CS-156-73, Comp. Sci. Dept., Univ. of Wisconsin, March 1973.
	2	Collins, G.E., Computer Algebra of Polynomials and Rational Functions, Am. Math. Monthly, Vol. 80, No. 7 (Aug.-Sept. 1973), pp. 725-755.
	3	George E. Collins, Hauptvortrag: Quantifier elimination for real closed fields by cylindrical algebraic decomposition, Proceedings of the 2nd GI Conference on Automata Theory and Formal Languages, p.134-183, May 20-23, 1975
	4	Collins, G.E., High-precision Calculation of Real Algebraic Numbers, in preparation.
	5	Collins, G.E., and Horowitz, E., The Minimum Root Separation of a Polynomial, Mathematics of Computation, Vol. 28, No. 126 (April, 1974), pp. 589-597.
	6	Lee E. Heindel, Integer Arithmetic Algorithms for Polynomial Real Zero Determination, Journal of the ACM (JACM), v.18 n.4, p.533-548, Oct. 1971 [doi>10.1145/321662.321667]
	7	Kac, M., Probability and Related Topics in Physical Sciences, Interscience Publishers, New York, 1959.
	8	Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
	9	Mignotte, M., An Inequality About Factors of Polynomials, Mathematics of Computation, Vol. 28, No. 128 (October, 1974), pp. 1153-1157.
	10	van der Waerden, B. L., Modern Algebra, Ungar Publishing Co., New York, 1948.

CITED BY 13

	J. R. Johnson, Real algebraic number computation using interval arithmetic, Papers from the international symposium on Symbolic and algebraic computation, p.195-205, July 27-29, 1992, Berkeley, California, United States
	Achim Schweikard, Real zero isolation for trigonometric polynomials, ACM Transactions on Mathematical Software (TOMS), v.18 n.3, p.350-359, Sept. 1992
	Siegfried Rump, On the sign of a real algebraic number, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.238-241, August 10-12, 1976, Yorktown Heights, New York, United States
	Alkiviadis G. Akritas, A new method for polynomial real root isolation, Proceedings of the 16th annual Southeast regional conference, p.39-43, April 13-15, 1978, Atlanta, Georgia
	Richard J. Fateman, An Algorithm for Deciding the Convergence of the Rational Iteration xn+1= f(xn), ACM Transactions on Mathematical Software (TOMS), v.3 n.3, p.272-278, Sept. 1977
	George E. Collins , Alkiviadis G. Akritas, Polynomial real root isolation using Descarte's rule of signs, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.272-275, August 10-12, 1976, Yorktown Heights, New York, United States
	Siegfried M. Rump, Real root isolation for algebraic polynomials, ACM SIGSAM Bulletin, v.11 n.2, p.2-3, May 1977
	Melanie Achatz , Scott McCallum , Volker Weispfenning, Deciding polynomial-exponential problems, Proceedings of the twenty-first international symposium on Symbolic and algebraic computation, July 20-23, 2008, Linz/Hagenberg, Austria
	Muresan Alexe Calin, The polynomial roots repartition and minimum roots separation, WSEAS Transactions on Mathematics, v.7 n.8, p.515-527, August 2008
	Muresan Alexe Calin, Isolating the polynomial roots with all zeros real, Proceedings of the 12th WSEAS international conference on Computers, p.360-365, July 23-25, 2008, Heraklion, Greece
	Calin Alexe Muresan, Cost reduction on roots pre-isolation, Proceedings of the 8th WSEAS international conference on Artificial intelligence, knowledge engineering and data bases, p.366-371, February 21-23, 2009, Cambridge, UK
	Andre Schollmeyer , Bernd Fröhlich, Direct trimming of NURBS surfaces on the GPU, ACM Transactions on Graphics (TOG), v.28 n.3, August 2009
	Calin Alexe Muresan, Comparative methods for the polynomial isolation, Proceedings of the WSEAES 13th international conference on Computers, p.634-638, July 23-25, 2009, Rodos, Greece