Computing roadmaps in smooth real algebraic sets

Abstract : Let (f1, . . . , fs) be polynomials in Q[X 1 , . . . , Xn ] of degree bounded by D that generate a radical equidimensional ideal of dimension d and let V ⊂ C^n be the locus of their complex zero set which is supposed to be smooth. A roadmap in V ∩ R^n is a real algebraic curve contained in V ∩ Rn which has a non-empty and connected intersection with each connected component of V ∩ R^n . The classical strategy to compute roadmaps is due to J. Canny and leads to algorithms having a complexity within D^O(n^2) arithmetic operations in Q. This strategy is based on computing a polar variety of dimension 1 and a recursion on the studied variety intersected with fibers taken above a critical value of a projection. Thus, it requires computations with real algebraic numbers and introduces singularities at each recursive call. Thus, no efficient implementation of roadmap algorithms have been obtained until now. Our aim is to provide an efficient implementation of the roadmap algorithm. We show how to slightly modify this strategy in order to avoid the use of real algebraic numbers and to deal with smooth algebraic sets at each recursive call in the case where the input variety is smooth. Our complexity is h^d D^O(n) operations in Q where h bounds the number of recursive call in our algorithm. This quantity is related to the geometry of V ∩ R^n and is bounded by D^O(n), thus in worst cases our algorithm has a complexity within D^O(n^2) arithmetic operations. We report on some experiments done with a preliminary implementation of our algorithm.
Type de document :
Communication dans un congrès
Jean-Guillaume Dumas. Transgressive Computing 2006, Apr 2006, Granada, Spain. pp.327-338, 2006
Liste complète des métadonnées

https://hal.inria.fr/hal-00818797
Contributeur : Marc Mezzarobba <>
Soumis le : lundi 29 avril 2013 - 11:12:53
Dernière modification le : vendredi 31 août 2018 - 09:25:58

Identifiants

  • HAL Id : hal-00818797, version 1

Collections

Citation

Marc Mezzarobba, Mohab Safey El Din. Computing roadmaps in smooth real algebraic sets. Jean-Guillaume Dumas. Transgressive Computing 2006, Apr 2006, Granada, Spain. pp.327-338, 2006. 〈hal-00818797〉

Partager

Métriques

Consultations de la notice

101