English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

New bounds for the Descartes method

MPS-Authors
/persons/resource/persons44838

Krandick,  Werner
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45021

Mehlhorn,  Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Krandick, W., & Mehlhorn, K. (2006). New bounds for the Descartes method. Journal of Symbolic Computation, 41(1), 49-66. doi:10.1016/j.jsc.2005.02.004.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-2384-C
Abstract
We 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.