# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Computing Real Roots of Real Polynomials

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

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

##### Fulltext (public)

1308.4088v2

(Preprint), 795KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Sagraloff, M., & Mehlhorn, K. (2013). Computing Real Roots of Real Polynomials. Retrieved from http://arxiv.org/abs/1308.4088.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0024-4591-A

##### Abstract

Computing the real roots of a polynomial is a fundamental problem of
computational algebra. We describe a variant of the Descartes method that
isolates the real roots of any real square-free polynomial given through
coefficient oracles. A coefficient oracle provides arbitrarily good
approximations of the coefficients. The bit complexity of the algorithm matches
the complexity of the best algorithm known, and the algorithm is simpler than
this algorithm. The algorithm derives its speed from the combination of
Descartes method with Newton iteration. Our algorithm can also be used to
further refine the isolating intervals to an arbitrary small size. The
complexity of root refinement is nearly optimal.