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)$.
Complete list of metadatas

https://hal.inria.fr/hal-01468796
Contributor : Sylvain Lazard <>
Submitted on : Wednesday, February 15, 2017 - 5:28:03 PM
Last modification on : Monday, June 3, 2019 - 9:20:02 AM
Long-term archiving on : Tuesday, May 16, 2017 - 3:26:56 PM

File

JSC.pdf
Files produced by the author(s)

Identifiers

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⟩

Share

Metrics

Record views

489

Files downloads

171