Sign Determination in Residue Number Systems

Abstract : Sign determination is a fundamental problem in algebraic as well as geometric computing. It is the critical operation when using real algebraic numbers and exact geometric predicates. We propose an exact and efficient method that determines the sign of a multivariate polynomial expression with rational coefficients. Exactness is achieved by using modular computation. Although this usually requires some multiprecision computation, our novel techniques of recursive relaxation of the moduli and their variants enable us to carry out sign determination and comparisons by using only single precision. Moreover, to exploit modern day hardware, we exclusively rely on floating point arithmetic, which leads us to a hybrid symbolic-numeric approach to exact arithmetic. We show how our method can be used to generate robust and efficient implementations of real algebraic and geometric algorithms including Sturm sequences, algebraic representation of points and curves, convex hull and Voronoi diagram computations and solid modeling. This method is highly parallelizable, easy to implement, and compares favorably with known multiprecision methods from a practical complexity point of view. We substantiate these claims by experimental results and comparisons to other existing approaches.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 1999, Special issue on Real Numbers and Computers, 210, pp.173-197
Liste complète des métadonnées

https://hal.inria.fr/inria-00344324
Contributeur : Sylvain Pion <>
Soumis le : jeudi 4 décembre 2008 - 14:43:36
Dernière modification le : mardi 17 avril 2018 - 11:48:04
Document(s) archivé(s) le : lundi 7 juin 2010 - 23:44:38

Fichier

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

Identifiants

  • HAL Id : inria-00344324, version 1

Collections

Citation

Hervé Brönnimann, Ioannis Emiris, Victor Y. Pan, Sylvain Pion. Sign Determination in Residue Number Systems. Theoretical Computer Science, Elsevier, 1999, Special issue on Real Numbers and Computers, 210, pp.173-197. 〈inria-00344324〉

Partager

Métriques

Consultations de la notice

278

Téléchargements de fichiers

101