Refereed Conference Paper

A Descartes Algorithm for Polynomials with Bit-Stream Coefficients. Arno Eigenwillig, Lutz Kettner, Werner Krandick, Kurt Mehlhorn, Susanne Schmitt, and Nicola Wolpert. In: Proc. 8th Int. Workshop on Computer Algebra in Scient. Comput. (CASC'05), Kalamata, Greece. LNCS 3718, Springer, 138--149, September, 2005.

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ⁿ+...+q₀ with root separation rho, coefficients |q_n| >= 1 and |q_i| <= 2^tau, it needs coefficient approximations to O(n(log(1/rho + tau)) bits after the binary point and has an expected cost of O(n⁴ (log(1/rho) + tau)²) bit operations.

[PDF] © Springer-Verlag
[PostScript] © Springer-Verlag
[EXACUS Home Page]