New bounds for the Descartes method

Krandick, Werner; Mehlhorn, Kurt

doi:10.1016/j.jsc.2005.02.004

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

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;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

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: https://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.