Univariate Algebraic Kernel and Application to Arrangements

Sylvain Lazard 1 Luis Peñaranda 1 Elias P. Tsigaridas 2
1 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
2 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 : We present a cgal-based univariate algebraic kernel, which provides certied real-root isolation of univariate polynomials with integer coecients and standard functionalities such as basic arithmetic operations, greatest common divisor (gcd) and square-free factorization, as well as comparison and sign evaluations of real algebraic numbers. We compare our kernel with other comparable kernels, demonstrating the eciency of our approach. Our experiments are performed on large data sets including polynomials of high degree (up to 2 000) and with very large coecients (up to 25 000 bits per coecient). We also address the problem of computing arrangements of x-monotone polynomial curves. We apply our kernel to this problem and demonstrate its eciency compared to previous solutions available in cgal.
Type de document :
Communication dans un congrès
Jan Vahrenhold. 8th International Symposium SEA 2009, Jun 2009, Dortmund, Germany. Springer-Verlag, LNCS 5526/2009, pp.209-220, 2009, Lecture Notes in Computer Science. 〈http://www.springerlink.com/content/86154423035p3265/?p=65a469d9bf0643db8b0d9da60f98bd60&pi=19〉. 〈10.1007/978-3-642-02011-7〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00431559
Contributeur : Sylvain Lazard <>
Soumis le : jeudi 12 novembre 2009 - 15:22:51
Dernière modification le : jeudi 11 janvier 2018 - 16:04:53
Document(s) archivé(s) le : mardi 16 octobre 2012 - 13:55:22

Fichier

sea09_final.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Sylvain Lazard, Luis Peñaranda, Elias P. Tsigaridas. Univariate Algebraic Kernel and Application to Arrangements. Jan Vahrenhold. 8th International Symposium SEA 2009, Jun 2009, Dortmund, Germany. Springer-Verlag, LNCS 5526/2009, pp.209-220, 2009, Lecture Notes in Computer Science. 〈http://www.springerlink.com/content/86154423035p3265/?p=65a469d9bf0643db8b0d9da60f98bd60&pi=19〉. 〈10.1007/978-3-642-02011-7〉. 〈inria-00431559〉

Partager

Métriques

Consultations de la notice

748

Téléchargements de fichiers

139