License
When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-7157
URL: http://drops.dagstuhl.de/opus/volltexte/2006/715/
Go to the corresponding Portal


Mehlhorn, Kurt ; Eigenwillig, Arno ; Kettner, Lutz ; Krandick, Werner ; Schmitt, Susanne ; Wolpert, Nicola

A Descartes Algorithms for Polynomials with Bit-Stream Coefficients

pdf-format:
Document 1.pdf (211 KB)


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.

BibTeX - Entry

@InProceedings{mehlhorn_et_al:DSP:2006:715,
  author =	{Kurt Mehlhorn and Arno Eigenwillig and Lutz Kettner and Werner Krandick and Susanne Schmitt and Nicola Wolpert},
  title =	{A Descartes Algorithms for Polynomials with Bit-Stream Coefficients},
  booktitle =	{Reliable Implementation of Real Number Algorithms: Theory and Practice},
  year =	{2006},
  editor =	{Peter Hertling and Christoph M. Hoffmann and Wolfram Luther and Nathalie Revol},
  number =	{06021},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2006/715},
  annote =	{Keywords: Root Isolation, Interval Arithmetic, Descartes Algorithm}
}

Keywords: Root Isolation, Interval Arithmetic, Descartes Algorithm
Seminar: 06021 - Reliable Implementation of Real Number Algorithms: Theory and Practice
Issue Date: 2006
Date of publication: 13.09.2006


DROPS-Home | Fulltext Search | Imprint Published by LZI