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
2 OURAGAN - OUtils de Résolution Algébriques pour la Géométrie et ses ApplicatioNs

We present an algorithm for computing a separating linear form of a system of bivariate polynomials with integer coefficients, that is a linear combination of the variables that takes different values when evaluated at distinct (complex) solutions of the system. In other words, a separating linear form defines a shear of the coordinate system that sends the algebraic system in generic position, in the sense that no two distinct solutions are vertically aligned. The computation of such linear forms is at the core of most algorithms that solve algebraic systems by computing rational parameterizations of the solutions and, moreover, the computation a separating linear form is the bottleneck of these algorithms, in terms of worst-case bit complexity. Given two bivariate polynomials of total degree at most $d$ with integer coefficients of bitsize at most~$\tau$, our algorithm computes a separating linear form in $\sOB(d^{8}+d^7\tau)$ bit operations in the worst case, where the previously known best bit complexity for this problem was $\sOB(d^{10}+d^9\tau)$ (where $\sO$ refers to the complexity where polylogarithmic factors are omitted and $O_B$ refers to the bit complexity).

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).

Mots clés: computer algebra; polynomial system solving; linear separating form

Domaines: Géométrie algorithmique [cs.CG]

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