Title | **A deterministic algorithm for isolating real roots of a real polynomial** |

Author(s) | Kurt Mehlhorn, Michael Sagraloff |

Type | Article in Journal |

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. |

Keywords | Real polynomial, Root isolation, Descartes’ rule of sign, Bitstream coefficients |

ISSN | 0747-7171 |

URL |
http://www.sciencedirect.com/science/article/pii/S0747717110001537 |

Language | English |

Journal | Journal of Symbolic Computation |

Volume | 46 |

Number | 1 |

Pages | 70 - 90 |

Year | 2011 |

Edition | 0 |

Translation |
No |

Refereed |
No |