Elias' Article

Random polynomials and expected complexity of bisection methods for real solving.
Ioannis Z. Emiris, André Galligo, and Elias P. Tsigaridas.
In Proc. 35th ACM Int'l Symp. on Symbolic & Algebraic Comp. (ISSAC), pp. 235–242, ACM, Munich, Germany, July 2010.

• Home
• Research
• Teaching
• Contact

Files:

[PDF] 385.8kB  [gzipped postscript] 291.6kB  

Abstract:

Our probabilistic analysis sheds light to the following questions: Why random polynomials seem to have few, and well separated real roots, on the average? Why exact algorithms for real root isolation may perform comparatively well or even better than numerical ones? We exploit results by Kac, and by Edelman and Kostlan, on the expected number of real roots, in order to estimate the root separation for i.i.d. coefficients following two zero-mean normal distributions: for $SO(2)$ polynomials, the $i$-th coefficient has variance $d \choose i$, whereas for Weyl polynomials its variance is $1/i!$. By applying results from statistical physics we obtain the expected complexity of the Sturm solver. Our bounds are two orders of magnitude tighter than the record worst-case ones. We also derive an output-sensitive bound in the worst case. The second part of the paper shows that the expected number of real roots of a degree $d$ polynomial in the Bernstein basis is $\sqrt2d\pm\OO(1)$, when the coefficients are i.i.d. variables with moderate standard deviation. Our paper concludes with experimental results which corroborate our analysis.

@InProceedings{egt-issac-2010,
  author =       {Ioannis~Z. Emiris and Andr\'e Galligo and
                  Elias~P. Tsigaridas},
  title =        {Random polynomials and expected complexity of
                  bisection methods for real solving},
  booktitle =    ISSAC_2010,
  year =         2010,
  address =      {Munich, Germany},
  month =        {July},
  publisher =    {ACM},
  editor =       "S. Watt",
  pages =        "235--242",
  abstract =     " Our probabilistic analysis sheds light to the
                  following questions: Why random polynomials seem to
                  have few, and well separated real roots, on the
                  average?  Why exact algorithms for real root
                  isolation may perform comparatively well or even
                  better than numerical ones?  We exploit results by
                  Kac, and by Edelman and Kostlan, on the expected
                  number of real roots, in order to estimate the root
                  separation for i.i.d.\ coefficients following two
                  zero-mean normal distributions: for $SO(2)$
                  polynomials, the $i$-th coefficient has variance ${d
                  \choose i}$, whereas for Weyl polynomials its
                  variance is ${1/i!}$.  By applying results from
                  statistical physics we obtain the expected
                  complexity of the Sturm solver.  Our bounds are two
                  orders of magnitude tighter than the record
                  worst-case ones.  We also derive an output-sensitive
                  bound in the worst case.  The second part of the
                  paper shows that the expected number of real roots
                  of a degree $d$ polynomial in the Bernstein basis is
                  $\sqrt{2d}\pm\OO(1)$, when the coefficients are
                  i.i.d.\ variables with moderate standard deviation.
                  Our paper concludes with experimental results which
                  corroborate our analysis.",
}

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