Elias' Article

Univariate real root isolation in multiple extension fields.
Adam Strzebo\'nski and Elias P. Tsigaridas.
In Proc. 37th ACM Int'l Symp. on Symbolic & Algebraic Comp. (ISSAC), pp. 343–350, ACM, Grenoble, France, July 2012.

• Home
• Research
• Teaching
• Contact

Files:

(unavailable)

Abstract:

We present algorithmic, complexity and implementation results for the problem of isolating the real roots of a univariate polynomial in $\Ba \in L[y]$, where $L=\QQ(\alpha_1, \dots, \alpha_\ell)$ is an algebraic extension of the rational numbers. Our bounds are single exponential in $\ell$ and match the ones presented in \citest-issac-2011 for the case $\ell=1$. We consider two approaches. The first, indirect approach, using multivariate resultants, computes a univariate polynomial with integer coefficients, among the real roots of which are the real roots of $\Ba$. The Boolean complexity of this approach is $\sOB(N^4\ell+4)$, where $N$ is the maximum of the degrees and the coefficient bitsize of the involved polynomials. The second, direct approach, tries to solve the polynomial directly, without reducing the problem to a univariate one. We present an algorithm that generalizes Sturm algorithm from the univariate case, and modified versions of well known solvers that are either numerical or based on Descartes' rule of sign. We achieve a Boolean complexity of $\sOB(\min\setN^4\ell + 7,N^2\ell^2+6)$ and $\sOB( N^2\ell+4)$, respectively. We implemented the algorithms in \funcC as part of the core library of \mathematica and we illustrate their efficiency over various data sets.

@InProceedings{st-issac-2012,
  author =       {Adam Strzebo\'nski and Elias~P. Tsigaridas},
  title =        {Univariate real root isolation in multiple extension
                  fields},
  booktitle =    ISSAC_2012,
  year =         2012,
  address =      {Grenoble, France},
  month =        {July},
  publisher =    {ACM},
  pages =        "343--350",
  abstract =     "We present algorithmic, complexity and
                  implementation results for the problem of isolating
                  the real roots of a univariate polynomial in $\Ba
                  \in L[y]$, where $L=\QQ(\alpha_1, \dots,
                  \alpha_{\ell})$ is an algebraic extension of the
                  rational numbers.  Our bounds are single exponential
                  in $\ell$ and match the ones presented in
                  \cite{st-issac-2011} for the case $\ell=1$.  We
                  consider two approaches. The first, indirect
                  approach, using multivariate resultants, computes a
                  univariate polynomial with integer coefficients,
                  among the real roots of which are the real roots of
                  $\Ba$. The Boolean complexity of this approach is
                  $\sOB(N^{4\ell+4})$, where $N$ is the maximum of the
                  degrees and the coefficient bitsize of the involved
                  polynomials.  The second, direct approach, tries to
                  solve the polynomial directly, without reducing the
                  problem to a univariate one. We present an algorithm
                  that generalizes Sturm algorithm from the univariate
                  case, and modified versions of well known solvers
                  that are either numerical or based on Descartes'
                  rule of sign.  We achieve a Boolean complexity of
                  $\sOB(\min\set{N^{4\ell + 7},N^{2\ell^2+6}})$ and
                  $\sOB( N^{2\ell+4})$, respectively.  We implemented
                  the algorithms in \func{C} as part of the core
                  library of \mathematica and we illustrate their
                  efficiency over various data sets.",
}

Generated by bib2html.pl (written by Patrick Riley , modified by Elias ) on Wed Oct 23, 2019 21:41:02