Improved algorithm for computing separating linear forms for bivariate systems

Abstract : We address the problem of computing a linear separating form of a system of two bivariate polynomials with integer coefficients, that is a linear combination of the variables that takes different values when evaluated at the distinct solutions of the system. 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 this is the bottleneck of these algorithms in terms of worst-case bit complexity. We present for this problem a new algorithm of worst-case bit complexity $\sOB(d^7+d^6\tau)$ where $d$ and $\tau$ denote respectively the maximum degree and bitsize of the input (and where $\sO$ refers to the complexity where polylogarithmic factors are omitted and $O_B$ refers to the bit complexity). This algorithm simplifies and decreases by a factor $d$ the worst-case bit complexity presented for this problem by Bouzidi et al. \cite{bouzidiJSC2014a}. This algorithm also yields, for this problem, a probabilistic Las-Vegas algorithm of expected bit complexity $\sOB(d^5+d^4\tau)$.
Type de document :
Communication dans un congrès
ISSAC - 39th International Symposium on Symbolic and Algebraic Computation, Jul 2014, Kobe, Japan. 2014
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00992634
Contributeur : Marc Pouget <>
Soumis le : lundi 19 mai 2014 - 10:08:38
Dernière modification le : mardi 10 octobre 2017 - 13:46:14
Document(s) archivé(s) le : lundi 10 avril 2017 - 23:32:12

Fichiers

separating_element_curve.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-00992634, version 1
  • ARXIV : 1405.4740

Collections

Citation

Yacine Bouzidi, Sylvain Lazard, Guillaume Moroz, Marc Pouget, Fabrice Rouillier. Improved algorithm for computing separating linear forms for bivariate systems. ISSAC - 39th International Symposium on Symbolic and Algebraic Computation, Jul 2014, Kobe, Japan. 2014. 〈hal-00992634〉

Partager

Métriques

Consultations de la notice

384

Téléchargements de fichiers

164