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
Abstract : 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 of 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+d^5\tau^2)$ 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).
Type de document :
Communication dans un congrès
ISSAC - 38th International Symposium on Symbolic and Algebraic Computation, Jun 2013, Boston, United States. pp.117-124, 2013
Liste complète des métadonnées


https://hal.inria.fr/hal-00809425
Contributeur : Sylvain Lazard <>
Soumis le : mardi 9 avril 2013 - 11:52:40
Dernière modification le : mardi 13 décembre 2016 - 15:42:10
Document(s) archivé(s) le : lundi 3 avril 2017 - 02:36:23

Fichier

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

Identifiants

  • HAL Id : hal-00809425, version 1

Collections

Citation

Yacine Bouzidi, Sylvain Lazard, Marc Pouget, Fabrice Rouillier. Separating Linear Forms for Bivariate Systems. ISSAC - 38th International Symposium on Symbolic and Algebraic Computation, Jun 2013, Boston, United States. pp.117-124, 2013. <hal-00809425>

Partager

Métriques

Consultations de
la notice

289

Téléchargements du document

124