Bivariate triangular decompositions in the presence of asymptotes

Abstract : Given two coprime polynomials $P$ and $Q$ in $\mathbb{Z}[x,y]$ of degree at most $d$ and coefficients of bitsize at most $\tau$, we address the problem of computing a triangular decomposition $\{(U_i(x),V_i(x,y))\}_{i\in\cal I}$ of the system $\{P,Q\}$. The state-of-the-art worst-case complexities for computing such triangular decompositions when the curves defined by the input polynomials do not have common vertical asymptotes are $\widetilde{O}(d^4)$ for the arithmetic complexity and $\widetilde{O}_B(d^{6} +d^{5}\tau)$ for the bit complexity, where $\widetilde{O}$ refers to the complexity where polylogarithmic factors are omitted and $O_B$ refers to the bit complexity. We show that the same worst-case complexities can be achieved even when the curves defined by the input polynomials may have common vertical asymptotes. We actually present refined complexities, $\widetilde{O}(d_xd_y^3+d_x^2d_y^2)$ for the arithmetic complexity and $\widetilde{O}_B(d_x^3d_y^3 + (d_x^2d_y^3+d_xd_y^4)\tau)$ for the bit complexity, where $d_x$ and $d_y$ bound the degrees of $P$ and $Q$ in $x$ and $y$, respectively. We also prove that the total bitsize of the decomposition is in $\widetilde{O}((d_x^2d_y^3+d_xd_y^4)\tau)$.
Type de document :
Article dans une revue
Journal of Symbolic Computation, Elsevier, 2017, 82, pp.123 - 133. <10.1016/j.jsc.2017.01.004>
Liste complète des métadonnées

https://hal.inria.fr/hal-01468796
Contributeur : Sylvain Lazard <>
Soumis le : mercredi 15 février 2017 - 17:28:03
Dernière modification le : mardi 20 juin 2017 - 01:06:49
Document(s) archivé(s) le : mardi 16 mai 2017 - 15:26:56

Fichier

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

Identifiants

Collections

Citation

Sylvain Lazard, Marc Pouget, Fabrice Rouillier. Bivariate triangular decompositions in the presence of asymptotes. Journal of Symbolic Computation, Elsevier, 2017, 82, pp.123 - 133. <10.1016/j.jsc.2017.01.004>. <hal-01468796>

Partager

Métriques

Consultations de
la notice

278

Téléchargements du document

37