Elias' Article

On the complexity of complex root isolation.
Bernard Mourrain and Elias P. Tsigaridas.
In Proc. 10th Int. Symp. on Effective Methods in Algebraic Geometry (MEGA), Barcelona, Spain, 2009.

• Home
• Research
• Teaching
• Contact

Files:

[PDF] 164.3kB  [gzipped postscript] 89.0kB  

Abstract:

We consider the problem of analyzing the complexity of isolating the complex roots of polynomials with Gaussian integers as coefficients. We provide a simplified proof for the number of steps that a subdivision-based algorithm performs. If $d$ is the degree of the polynomial and $\tau$ the maximum coefficient bitsize, then we prove a bound of $\sOB( d^7 + d^6 \tau + d^5 \tau^2)$, for algorithms based on Sturm sequences, thus improving the previously known by a factor.

@InProceedings{mt-mega-2009,
  author =       {Bernard Mourrain and Elias~P. Tsigaridas},
  title =        {On the complexity of complex root isolation},
  booktitle =    {Proc. 10th Int. Symp. on Effective Methods in
                  Algebraic Geometry (MEGA)},
  year =         2009,
  address =      {Barcelona, Spain},
  abstract =     " We consider the problem of analyzing the complexity
                  of isolating the complex roots of polynomials with
                  Gaussian integers as coefficients.  We provide a
                  simplified proof for the number of steps that a
                  subdivision-based algorithm performs.  If $d$ is the
                  degree of the polynomial and $\tau$ the maximum
                  coefficient bitsize, then we prove a bound of $\sOB(
                  d^7 + d^6 \tau + d^5 \tau^2)$, for algorithms based
                  on Sturm sequences, thus improving the previously
                  known by a factor.",
}

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