Files:

[PDF] 254.7kB  [gzipped postscript] 223.4kB  

Abstract:

Real solving of univariate polynomials is a fundamental problem with several important applications. This paper is focused on the comparison of black-box implementations of state-of-the-art algorithms for isolating real roots of univariate polynomials over the integers. We have tested $9$ different implementations based on symbolic-numeric methods, Sturm sequences, Continued Fractions and Descartes' rule of sign. The methods under consideration were developed at the GALAAD group at \inria, the VEGAS group at łoria and the \mpi-Saarbrücken. We compared their sensitivity with respect to various aspects such as degree, bitsize or root separation of the input polynomials. Our datasets consist of $5000$ polynomials from many different settings, which have maximum coefficient bitsize up to bits $8000$, and the total running time of the experiments was about $50$ hours. Thereby, all implementations of the theoretically exact methods always provided correct results throughout this extensive study. For each scenario we identify the currently most adequate method, and we point to weaknesses in each approach, which should lead to further improvements. Our results indicate that there is no “best method” overall, but one can say that for most instances the solvers based on Continued Fractions are among the best methods. To the best of our knowledge, this is the largest number of tests for univariate real solving up to date.

BibTeX:
@InProceedings{ehkmtz-snc-2009,
  author =       {Hemmer, Michael and Tsigaridas, Elias P. and
                  Zafeirakopoulos, Zafeirakis and Emiris, Ioannis
                  Z. and Karavelas, Menelaos I. and Mourrain, Bernard},
  title =        {Experimental evaluation and cross-benchmarking of
                  univariate real solvers},
  booktitle =    SNC_2009,
  year =         2009,
  isbn =         {978-1-60558-664-9},
  pages =        {45--54},
  location =     {Kyoto, Japan},
  publisher =    {ACM},
  address =      {New York, NY, USA},
  editor =       {H. Kai and H. Sekigawa},
  abstract =     "Real solving of univariate polynomials is a
                  fundamental problem with several important
                  applications.  This paper is focused on the
                  comparison of black-box implementations of
                  state-of-the-art algorithms for isolating real roots
                  of univariate polynomials over the integers.  We
                  have tested $9$ different implementations based on
                  symbolic-numeric methods, Sturm sequences, Continued
                  Fractions and Descartes' rule of sign.  The methods
                  under consideration were developed at the GALAAD
                  group at \inria, the VEGAS group at \loria\ and the
                  \mpi-Saarbr{\"u}cken.  We compared their sensitivity
                  with respect to various aspects such as degree,
                  bitsize or root separation of the input polynomials.
                  Our datasets consist of $5\,000$ polynomials from
                  many different settings, which have maximum
                  coefficient bitsize up to bits $8\,000$, and the
                  total running time of the experiments was about $50$
                  hours.  Thereby, all implementations of the
                  theoretically exact methods always provided correct
                  results throughout this extensive study.  For each
                  scenario we identify the currently most adequate
                  method, and we point to weaknesses in each approach,
                  which should lead to further improvements.  Our
                  results indicate that there is no ``best method''
                  overall, but one can say that for most instances the
                  solvers based on Continued Fractions are among the
                  best methods.  To the best of our knowledge, this is
                  the largest number of tests for univariate real
                  solving up to date.",
}

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