Elias' Article

Real Algebraic Numbers: Complexity Analysis and Experimentation.
Ioannis Z. Emiris, Bernard Mourrain, and Elias P. Tsigaridas.
In Reliable Implementations of Real Number Algorithms: Theory and Practice, pp. 57–82, LNCS 5045, Springer Verlag, 2008. (also available in www.inria.fr/rrrt/rr-5897.html)

• Home
• Research
• Teaching
• Contact

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.

@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 Wed Oct 23, 2019 21:41:02