hide
Free keywords:
-
Abstract:
We describe a bisection algorithm for root isolation of polynomials with real
coefficients. It is assumed that the coefficients can be approximated with
arbitrary precision; exact computation in the field of coefficients is not
required. We refer to such coefficients as bitstream coefficients. The
algorithm is simpler, deterministic and has better asymptotic complexity than
the randomized algorithm of Eigenwillig et al. (2005). We also discuss a
partial extension to multiple roots.