# Bivariate triangular decompositions in the presence of asymptotes

1 GAMBLE - Geometric Algorithms and Models Beyond the Linear and Euclidean realm
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
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〉
Domaine :

https://hal.inria.fr/hal-01468796
Contributeur : Sylvain Lazard <>
Soumis le : mercredi 15 février 2017 - 17:28:03
Dernière modification le : vendredi 4 janvier 2019 - 17:33:34
Document(s) archivé(s) le : mardi 16 mai 2017 - 15:26:56

### Fichier

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

### 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〉

### Métriques

Consultations de la notice

## 440

Téléchargements de fichiers