Separating linear forms for bivariate systems

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 présentons un algorithme pour calculer une forme linéaire séparante d'un systéme de polynômes á deux variables á coefficients entiers, 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. En d'autres termes, une forme linéaire séparante définit un changement de coordonnées qui met le systéme algébrique en position générique, au sens oú deux solutions distinctes ne sont jamais verticalement alignées. Le calcul de ces formes linéaires est au coeur de la plupart des algorithmes qui permettent de résoudre des systémes algébriques au moyen de paramétrisations rationnelles des solutions et, de plus, le calcul d'une forme linéaire séparante domine la complexité binaire de ces algorithmes. Etant donnés deux polynômes á deux variables de degré total au plus $ d $ avec des coefficients entiers de taille binaire au plus $ \tau $, notre algorithme calcule une forme linéaire séparante en $\sOB(d^{8}+d^7\tau)$ opérations binaires dans le pire des cas, améliorant la meilleure complexité connue pour ce probléme d'un facteur $d^2$ (oú $ \sO $ se référe á la complexité oú les facteurs polylogarithmiques sont omis et $O_B$ se référe á la complexité binaire).
Type de document :
Rapport
[Research Report] RR-8261, INRIA. 2013, pp.20
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00802693
Contributeur : Marc Pouget <>
Soumis le : lundi 20 janvier 2014 - 00:41:08
Dernière modification le : mardi 10 octobre 2017 - 13:44:37
Document(s) archivé(s) le : lundi 21 avril 2014 - 01:05:12

Fichiers

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

Identifiants

  • HAL Id : hal-00802693, version 2
  • ARXIV : 1303.5041

Citation

Yacine Bouzidi, Sylvain Lazard, Marc Pouget, Fabrice Rouillier. Separating linear forms for bivariate systems. [Research Report] RR-8261, INRIA. 2013, pp.20. 〈hal-00802693v2〉

Partager

Métriques

Consultations de
la notice

407

Téléchargements du document

124