Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleNew bounds for the Descartes method
Author(s) Werner Krandick, Kurt Mehlhorn
TypeArticle in Journal
AbstractWe give a new bound for the number of recursive subdivisions in the Descartes method for polynomial real root isolation. Our proof uses Ostrowski’s theory of normal power series from 1950 which has so far been overlooked in the literature. We combine Ostrowski’s results with a theorem of Davenport from 1985 to obtain our bound. We also characterize normality of cubic polynomials by explicit conditions on their roots and derive a generalization of one of Ostrowski’s theorems.
KeywordsPolynomial real root isolation, Descartes rule of signs, Modified Uspensky method, Recursion tree analysis, Normal polynomials, Root separation bounds, History of mathematics, Möbius transformations, Coefficient sign variations, Cylindrical algebraic deco
URL http://www.sciencedirect.com/science/article/pii/S0747717105001252
JournalJournal of Symbolic Computation
Pages49 - 66
Translation No
Refereed No