Experimental evaluation and cross-benchmarking of univariate real solvers

Ioannis Z. Emiris 1, 2 Michael Hemmer 3 Menelaos Karavelas 4 Bernard Mourrain 5 Elias P. Tsigaridas 5 Zafeirakis Zafeirakopoulos 6
1 AROMATH - AlgebRe, geOmetrie, Modelisation et AlgoriTHmes
CRISAM - Inria Sophia Antipolis - Méditerranée , National and Kapodistrian University of Athens
5 GALAAD - Geometry, algebra, algorithms
CRISAM - Inria Sophia Antipolis - Méditerranée , UNS - Université Nice Sophia Antipolis, CNRS - Centre National de la Recherche Scientifique : UMR6621
Abstract : Real solving of univariate polynomials is a fundamental problem with several important applications. This paper focuses on the efficient and generic black-box implementations of state-of-the-art algorithms for isolating all real roots of polynomials with integer coefficients, motivated by geometric applications and the recent need to develop software that handles exactly complex geometric objects, particularly in the case of the \cgal\ library. We summarize a large set of experimental results from cross-benchmarking 3 univariate algebraic kernels developed at the GALAAD group at INRIA, MPI-Saarbrücken, and the VEGAS group at LORIA. We have tested~6 solvers from the INRIA kernel, which are based on Sturm sequences, symbolic-numeric methods, and Continued Fractions (CF); two solvers from the MPI kernel, namely \descartes\ and \bdescartes; and one solver from the LORIA kernel, relying on the Descartes-based \rs\ solver developed at the SALSA group of INRIA. We used a total of~5000 polynomials of 5 types and various degrees and bitsizes, distributed in 150 datasets. The CF family of solvers, \descartes, \bdescartes, and \rs\ are numerically and combinatorially robust, i.e., they always provide the correct results. With respect to speed, the results are not decisive in most cases; overall, two CF methods seem faster, even though currently they do not use symbolic-numeric techniques, while for very large bitsizes \bdescartes\ and \rs\ seem more efficient, provided the degree is not very high. For polynomials of degree up to~4 and moderate bitsize, special algorithms give better results. It is important to note that the implementations of the theoretically exact methods are complete, efficient and they never provided wrong results throughout this extensive benchmarking procedure. Lastly, we comment on the different programming design approaches adopted by the different kernels, including the degree of interoperability between different algorithmic components, as well as arithmetic data types.
Complete list of metadatas

Cited literature [1 references]  Display  Hide  Download

https://hal.inria.fr/inria-00340887
Contributor : Elias Tsigaridas <>
Submitted on : Friday, June 5, 2009 - 6:27:16 PM
Last modification on : Monday, July 1, 2019 - 4:54:03 PM
Long-term archiving on : Wednesday, September 22, 2010 - 12:18:00 PM

File

RR-6954.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Ioannis Z. Emiris, Michael Hemmer, Menelaos Karavelas, Bernard Mourrain, Elias P. Tsigaridas, et al.. Experimental evaluation and cross-benchmarking of univariate real solvers. International Workshop SNC, ACM, Aug 2009, Kyoto, Japan. pp.85-94, ⟨10.1145/1577190.1577202⟩. ⟨inria-00340887v2⟩

Share

Metrics

Record views

686

Files downloads

491