DROPS

Document

A Descartes Algorithms for Polynomials with Bit-Stream Coefficients

Authors: Kurt Mehlhorn, Arno Eigenwillig, Lutz Kettner, Werner Krandick, Susanne Schmitt, and Nicola Wolpert

Published in: Dagstuhl Seminar Proceedings, Volume 6021, Reliable Implementation of Real Number Algorithms: Theory and Practice (2006)

Abstract

The Descartes method is an algorithm for isolating the real roots of square-free polynomials with real coefficients. We assume that coefficients are given as (potentially infinite) bit-streams. In other words, coefficients can be approximated to any desired accuracy, but are not known exactly. We show that a variant of the Descartes algorithm can cope with bit-stream coefficients. To isolate the real roots of a square-free real polynomial $q(x) = q_nx^n+ldots+q_0$ with root separation $ ho$, coefficients $abs{q_n}ge1$ and $abs{q_i} le 2^ au$, it needs coefficient approximations to $O(n(log(1/ ho) + au))$ bits after the binary point and has an expected cost of $O(n^4 (log(1/ ho) + au)^2)$ bit operations.

Cite as

Kurt Mehlhorn, Arno Eigenwillig, Lutz Kettner, Werner Krandick, Susanne Schmitt, and Nicola Wolpert. A Descartes Algorithms for Polynomials with Bit-Stream Coefficients. In Reliable Implementation of Real Number Algorithms: Theory and Practice. Dagstuhl Seminar Proceedings, Volume 6021, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{mehlhorn_et_al:DagSemProc.06021.3,
  author =	{Mehlhorn, Kurt and Eigenwillig, Arno and Kettner, Lutz and Krandick, Werner and Schmitt, Susanne and Wolpert, Nicola},
  title =	{{A Descartes Algorithms for Polynomials with Bit-Stream Coefficients}},
  booktitle =	{Reliable Implementation of Real Number Algorithms: Theory and Practice},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6021},
  editor =	{Peter Hertling and Christoph M. Hoffmann and Wolfram Luther and Nathalie Revol},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06021.3},
  URN =		{urn:nbn:de:0030-drops-7157},
  doi =		{10.4230/DagSemProc.06021.3},
  annote =	{Keywords: Root Isolation, Interval Arithmetic, Descartes Algorithm}
}

Search Results

Documents authored by Kettner, Lutz

A Descartes Algorithms for Polynomials with Bit-Stream Coefficients

Abstract

Cite as

Thanks for your feedback!

Could not send message