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