A Deterministic Algorithm for Isolating Real Roots of a Real Polynomial

Mehlhorn, Kurt; Sagraloff, Michael

doi:10.1016/j.jsc.2010.09.004

Datensatz

DATENSATZ AKTIONENEXPORT

Zur Ablage hinzufügen

Lokale TagsFreigabegeschichteDetailsÜbersicht

Freigegeben

Zeitschriftenartikel

A Deterministic Algorithm for Isolating Real Roots of a Real Polynomial

MPG-Autoren

/persons/resource/persons45021

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

/persons/resource/persons45332

Sagraloff, Michael
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen

Es sind keine externen Ressourcen hinterlegt

Volltexte (beschränkter Zugriff)

Für Ihren IP-Bereich sind aktuell keine Volltexte freigegeben.

Volltexte (frei zugänglich)

Es sind keine frei zugänglichen Volltexte in PuRe verfügbar

Ergänzendes Material (frei zugänglich)

Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar

Zitation

Mehlhorn, K., & Sagraloff, M. (2011). A Deterministic Algorithm for Isolating Real Roots of a Real Polynomial. Journal of Symbolic Computation, 46(1), 70-90. doi:10.1016/j.jsc.2010.09.004.

Zitierlink: https://hdl.handle.net/11858/00-001M-0000-0010-11DA-7

Zusammenfassung

We describe a bisection algorithm for root isolation of polynomials with real coefficients. It is assumed that the coefficients can be approximated with arbitrary precision; exact computation in the field of coefficients is not required. We refer to such coefficients as bitstream coefficients. The algorithm is simpler, deterministic and has better asymptotic complexity than the randomized algorithm of Eigenwillig et al. (2005). We also discuss a partial extension to multiple roots.