On the Complexity of Reliable Root Approximation

Kerber, Michael

doi:10.1007/978-3-642-04103-7_15

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Conference Paper

On the Complexity of Reliable Root Approximation

MPS-Authors

/persons/resource/persons44759

Kerber, Michael
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

Kerber, M. (2009). On the Complexity of Reliable Root Approximation. In V. Gerdt, E. Mayr, & E. Vorozhtsov (Eds.), Computer Algebra in Scientific Computing (pp. 155-167). Berlin: Springer. doi:10.1007/978-3-642-04103-7_15.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-1899-4

Abstract

This work addresses the problem of computing a certified ε-approximation of all real roots of a square-free integer polynomial. We proof an upper bound for its bit complexity, by analyzing an algorithm that first computes isolating intervals for the roots, and subsequently refines them using Abbott’s Quadratic Interval Refinement method. We exploit the eventual quadratic convergence of the method. The threshold for an interval width with guaranteed quadratic convergence speed is bounded by relating it to well-known algebraic quantities.