Bivariate triangular decompositions in the presence of asymptotes. (September 2017)

• Record Type: Journal Article
• Authors: Lazard, Sylvain; Pouget, Marc; Rouillier, Fabrice
• Is Part Of: Journal of symbolic computation. Volume 82(2017)
• Page Start: 123
• Page End: 133
• Publication Date: 2017-09
• Subjects: Polynomial system solving -- Bivariate system -- Triangular decomposition -- Asymptotes; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2017.01.004
• Languages: English
• ISSNs: 0747-7171

Abstract

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 ) τ ) .