Experimental evaluation and cross-benchmarking of univariate real solvers

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.
Type de document :
Communication dans un congrès
Hiroshi Kai, Hiroshi Sekigawa. International Workshop SNC, Aug 2009, Kyoto, Japan. pp.85-94, 2009, 〈10.1145/1577190.1577202〉
Liste complète des métadonnées

Littérature citée [1 références]  Voir  Masquer  Télécharger

Contributeur : Elias Tsigaridas <>
Soumis le : vendredi 5 juin 2009 - 18:27:16
Dernière modification le : jeudi 11 janvier 2018 - 16:03:48
Document(s) archivé(s) le : mercredi 22 septembre 2010 - 12:18:00


Fichiers produits par l'(les) auteur(s)



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



Consultations de la notice


Téléchargements de fichiers