Bivariate triangular decompositions in the presence of asymptotes. (September 2017) - Lazard, Sylvain; Pouget, Marc; Rouillier, Fabrice
Abstract: Given two coprime polynomials P and Q in Z [ x, y ] of degree at most d and coefficients of bitsize at most τ, we address the problem of computing a triangular decomposition { ( U i ( x ), V i ( x, y ) ) } i ∈ 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 O ˜ ( d 4 ) for the arithmetic complexity and O ˜ B ( d 6 + d 5 τ ) for the bit complexity, where 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, O ˜ ( d x d y 3 + d x 2 d y 2 ) for the arithmetic complexity and O ˜ B ( d x 3 d y 3 + ( d x 2 d y 3 + d x d y 4 ) τ ) 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 O ˜ ( ( d x 2 d y 3 + d x d y 4 ) τ ) .