Polynomial real root isolation using Descarte's rule of signs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Polynomial real root isolation using Descarte's rule of signs

Full text

Pdf (345 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: 272 - 275

Year of Publication: 1976

Authors

George E. Collins
Alkiviadis G. Akritas

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 18, Downloads (12 Months): 80, Citation Count: 34

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.806346 What is a DOI?

ABSTRACT

Uspensky's 1948 book on the theory of equations presents an algorithm, based on Descartes' rule of signs, for isolating the real roots of a squarefree polynomial with real coefficients. Programmed in SAC-1 and applied to several classes of polynomials with integer coefficients, Uspensky's method proves to be a strong competitor of the recently discovered algorithm of Collins and Loos. It is shown, however, that it's maximum computing time is exponential in the coefficient length. This motivates a modification of the Uspensky algorithm which is quadratic in the coefficient length and which also performs well in the practical test cases.

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	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	G. E. Collins and E. Horowitz, The Minimum Root Separation of a Polynomial, Math. Comp., Vol. 28, No. 126 (April 1974), 589-597.
	3	George E. Collins , Rüdiger Loos, Polynomial real root isolation by differentiation, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.15-25, August 10-12, 1976, Yorktown Heights, New York, United States [doi>10.1145/800205.806319]
	4	Lee Edward Heindel, Algorithms for exact polynomial root calculation, 1971
	5	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]
	6	J. V. Uspensky, Theory of Equations, McGraw-Hill, 1948.
	7	M. Vinent, Sur la Résolution des Équations Numeriques, Jour. de Mathematiques Pures et Appliquees, Vol. 1 (1836), 341-372.

CITED BY 34

	Achim Schweikard, Real zero isolation for trigonometric polynomials, ACM Transactions on Mathematical Software (TOMS), v.18 n.3, p.350-359, Sept. 1992
	Alkiviadis G. Akritis, There is no “Uspensky's method.”, Proceedings of the fifth ACM symposium on Symbolic and algebraic computation, p.88-90, July 21-23, 1986, Waterloo, Ontario, Canada
	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
	G. E. Collins , J. R. Johnson, Quantifier elimination and the sign variation method for real root isolation, Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation, p.264-271, July 17-19, 1989, Portland, Oregon, United States
	Jeremy R. Johnson , Werner Krandick , Anatole D. Ruslanov, Architecture-aware classical Taylor shift by 1, Proceedings of the 2005 international symposium on Symbolic and algebraic computation, p.200-207, July 24-27, 2005, Beijing, China
	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
	Pat Hanrahan, Ray tracing algebraic surfaces, ACM SIGGRAPH Computer Graphics, v.17 n.3, p.83-90, July 1983
	J. R. Johnson , Werner Krandick, Polynomial real root isolation using approximate arithmetic, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.225-232, July 21-23, 1997, Kihei, Maui, Hawaii, United States
	D. Kalra , A. H. Barr, Guaranteed ray intersections with implicit surfaces, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.297-306, July 1989
	George E. Collins, Polynomial minimum root separation, Journal of Symbolic Computation, v.32 n.5, p.467-473, November 2001
	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 , Werner Krandick, Multiprecision floating point addition, Proceedings of the 2000 international symposium on Symbolic and algebraic computation, p.71-77, July 2000, St. Andrews, Scotland
	George E. Collins , Jeremy R. Johnson , Werner Krandick, Interval arithmetic in cylindrical algebraic decomposition, Journal of Symbolic Computation, v.34 n.2, p.145-157, August 2002
	Fabrice Rouillier , Paul Zimmermann, Efficient isolation of polynomial's real roots, Journal of Computational and Applied Mathematics, v.162 n.1, p.33-50, 1 January 2004
	Willem F. Bronsvoort , Fopke Klok, Ray tracing generalized cylinders, ACM Transactions on Graphics (TOG), v.4 n.4, p.291-303, Oct. 1985
	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
	J H Davenport, A :20piano movers' ', ACM SIGSAM Bulletin, v.20 n.1-2, p.15-17, Feb/May 1986
	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
	Jeremy R. Johnson , Werner Krandick , Kevin Lynch , David G. Richardson , Anatole D. Ruslanov, High-performance implementations of the Descartes method, Proceedings of the 2006 international symposium on Symbolic and algebraic computation, July 09-12, 2006, Genoa, Italy
	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
	Arno Eigenwillig , Vikram Sharma , Chee K. Yap, Almost tight recursion tree bounds for the Descartes method, Proceedings of the 2006 international symposium on Symbolic and algebraic computation, July 09-12, 2006, Genoa, Italy
	Arno Eigenwillig, Short Communication: On multiple roots in Descartes' Rule and their distance to roots of higher derivatives, Journal of Computational and Applied Mathematics, v.200 n.1, p.226-230, March, 2007
	Xiaolei Zhang , Renhong Wang, Isolating the real roots of the piecewise algebraic variety, Computers & Mathematics with Applications, v.57 n.4, p.565-570, February, 2009
	Elias P. Tsigaridas , Ioannis Z. Emiris, On the complexity of real root isolation using continued fractions, Theoretical Computer Science, v.392 n.1-3, p.158-173, February, 2008
	Victor Y. Pan , Brian Murphy , Rhys Eric Rosholt , Guoliang Qian , Yuqing Tang, Real root-finding, Proceedings of the 2007 international workshop on Symbolic-numeric computation, July 25-27, 2007, London, Ontario, Canada
	Arno Eigenwillig , Michael Kerber , Nicola Wolpert, Fast and exact geometric analysis of real algebraic plane curves, Proceedings of the 2007 international symposium on Symbolic and algebraic computation, July 29-August 01, 2007, Waterloo, Ontario, Canada
	Vikram Sharma, Complexity of real root isolation using continued fractions, Proceedings of the 2007 international symposium on Symbolic and algebraic computation, July 29-August 01, 2007, Waterloo, Ontario, Canada
	Jin-San Cheng , Xiao-Shan Gao , Chee-Keng Yap, Complete numerical isolation of real zeros in zero-dimensional triangular systems, Proceedings of the 2007 international symposium on Symbolic and algebraic computation, July 29-August 01, 2007, Waterloo, Ontario, Canada
	Vikram Sharma, Complexity of real root isolation using continued fractions, Theoretical Computer Science, v.409 n.2, p.292-310, December, 2008
	Abel J. P. Gomes , José F. M. Morgado , Edgar S. Pereira, A BSP-based algorithm for dimensionally nonhomogeneous planar implicit curves with topological guarantees, ACM Transactions on Graphics (TOG), v.28 n.2, p.1-24, April 2009
	Ligang Liu , Lei Zhang , Binbin Lin , Guojin Wang, Fast approach for computing roots of polynomials using cubic clipping, Computer Aided Geometric Design, v.26 n.5, p.547-559, June, 2009
	Kurt Mehlhorn , Michael Sagraloff, Isolating real roots of real polynomials, Proceedings of the 2009 international symposium on Symbolic and algebraic computation, July 28-31, 2009, Seoul, Republic of Korea
	Michael Hemmer , Elias P. Tsigaridas , Zafeirakis Zafeirakopoulos , Ioannis Z. Emiris , Menelaos I. Karavelas , Bernard Mourrain, Experimental evaluation and cross-benchmarking of univariate real solvers, Proceedings of the 2009 conference on Symbolic numeric computation, August 03-05, 2009, Kyoto, Japan
	Iurie Caraus , Ion Necoara, A cutting plane method for solving convex optimization problems over the cone of nonnegative polynomials, WSEAS Transactions on Mathematics, v.8 n.7, p.269-278, July 2009