License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.06021.3
URN: urn:nbn:de:0030-drops-7157
URL: http://dagstuhl.sunsite.rwth-aachen.de/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:
06021.MehlhornKurt.Paper.715.pdf (0.2 MB)

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: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/opus/volltexte/2006/715},
  URN =		{urn:nbn:de:0030-drops-7157},
  doi =		{10.4230/DagSemProc.06021.3},
  annote =	{Keywords: Root Isolation, Interval Arithmetic, Descartes Algorithm}
}

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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI