##### Files:

[PDF] 474.6kB [gzipped postscript] 496.1kB

##### Abstract:

We present algorithmic, complexity and implementation results concerning real root isolation of a polynomial of degree $d$, with integer coefficients of bit size $łe \tau$, using Sturm (-Habicht) sequences and the Bernstein subdivision solver. %% In particular, we unify and simplify the analysis of both methods and we give an asymptotic complexity bound of $\sOB( d^4 \tau^2)$. This matches the best known bounds for binary subdivision solvers. Moreover, we generalize this to cover the non square-free polynomials and show that within the same complexity we can also compute the multiplicities of the roots. %% We also consider algorithms for sign evaluation, comparison of real algebraic numbers and simultaneous inequalities, and we improve the known bounds at least by a factor of $d$. Finally, we present our \textttC++ implementation in \synaps and some preliminary experiments on various data sets.

##### BibTeX:

@InProceedings{emt-lncs-2006, Author = {Ioannis~Z. Emiris and Bernard Mourrain and Elias~P. Tsigaridas}, Title = {{Real Algebraic Numbers: Complexity Analysis and Experimentation}}, BookTitle = {{Reliable Implementations of Real Number Algorithms: Theory and Practice}}, Series = "LNCS", volume = 5045, pages = {57--82}, Editor = {Hertling, P. and Hoffmann, C. and Luther, W. and Revol, N.}, Publisher = "Springer Verlag", year = 2008, note = "(also available in www.inria.fr/rrrt/rr-5897.html)", abstract = "We present algorithmic, complexity and implementation results concerning real root isolation of a polynomial of degree $d$, with integer coefficients of bit size $\le \tau$, using Sturm (-Habicht) sequences and the Bernstein subdivision solver. %% In particular, we unify and simplify the analysis of both methods and we give an asymptotic complexity bound of $\sOB( d^4 \tau^2)$. This matches the best known bounds for binary subdivision solvers. Moreover, we generalize this to cover the non square-free polynomials and show that within the same complexity we can also compute the multiplicities of the roots. %% We also consider algorithms for sign evaluation, comparison of real algebraic numbers and simultaneous inequalities, and we improve the known bounds at least by a factor of $d$. Finally, we present our \texttt{C++} implementation in \synaps and some preliminary experiments on various data sets.", }

Generated by bib2html.pl (written by Patrick Riley , modified by Elias ) on Mon Mar 12, 2018 14:23:33