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 Feb 06, 2017 11:45:57