Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal

Details:

   
TitleA deterministic algorithm for isolating real roots of a real polynomial
Author(s) Kurt Mehlhorn, Michael Sagraloff
TypeArticle in Journal
AbstractWe 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.
KeywordsReal polynomial, Root isolation, Descartes’ rule of sign, Bitstream coefficients
ISSN0747-7171
URL http://www.sciencedirect.com/science/article/pii/S0747717110001537
LanguageEnglish
JournalJournal of Symbolic Computation
Volume46
Number1
Pages70 - 90
Year2011
Edition0
Translation No
Refereed No
Webmaster