Mehlhorn, Kurt ;
Eigenwillig, Arno ;
Kettner, Lutz ;
Krandick, Werner ;
Schmitt, Susanne ;
Wolpert, Nicola
A Descartes Algorithms for Polynomials with Bit-Stream Coefficients
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 |
