Rational Univariate Representations of Bivariate Systems and Applications

Yacine Bouzidi 1 Sylvain Lazard 1 Marc Pouget 1 Fabrice Rouillier 2
1 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Résumé : Nous abordons le probléme de la résolution de systémes de deux polynômes á deux variables de degré total au plus $d $ á coefficients entiers de bitsize maximale $ \tau $. Il est connu que une forme linéaire séparante, c'est-á-dire une combinaison linéaire des variables qui prend des valeurs différentes quand elle est évaluée en des solutions (complexes) distinctes du systéme, peut être calculée en \comp\ bits opérations (oú $ \sO $ se référe á la complexité oú les facteurs polylogarithmiques sont omis et $O_B$ se référe á la complexité binaire) et nous nous concentrons ici sur le calcul d'une représentation univariée rationnelle (RUR) étant donné une forme linéaire séparante. Nous présentons un algorithme pour le calcul d'une RUR de complexité $ \sOB (d^7 + d^6 \tau) $ dans le pire cas et nous bornons la taille de ses coefficients par $ \sO(d^2 + d\tau) $. Nous montrons en outre que des boîtes d'isolation des solutions du systéme peuvent être calculées á partir de la RUR avec \comp\ bits opérations. Enfin, nous montrons comment une RUR peut être utilisée pour évaluer le signe d'un polynôme á deux variables (de degré au plus $ d $ et bitsize au plus $ \tau $) en une solution réelle du systéme en \comp\ bits opérations et en toutes les $ \Theta(d^2) $ solutions réelles en seulement $ O(d) $ fois plus que pour une solution.
Type de document :
Rapport
[Research Report] RR-8262, INRIA. 2013, pp.26
Liste complète des métadonnées


https://hal.inria.fr/hal-00802698
Contributeur : Marc Pouget <>
Soumis le : lundi 25 novembre 2013 - 09:40:11
Dernière modification le : jeudi 22 septembre 2016 - 14:31:21
Document(s) archivé(s) le : mercredi 26 février 2014 - 04:23:47

Fichiers

RR-8262.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00802698, version 2
  • ARXIV : 1303.5042

Citation

Yacine Bouzidi, Sylvain Lazard, Marc Pouget, Fabrice Rouillier. Rational Univariate Representations of Bivariate Systems and Applications. [Research Report] RR-8262, INRIA. 2013, pp.26. <hal-00802698v2>

Partager

Métriques

Consultations de
la notice

395

Téléchargements du document

130