Skip to Main content Skip to Navigation
Journal articles

Computing Puiseux series: a fast divide and conquer algorithm

Abstract : Let $F ∈ K[X, Y ]$ be a polynomial of total degree D defined over a field K of characteristic zero or greater than D. Assuming F separable with respect to Y , we provide an algorithm that computes all Puiseux series of F above X = 0 in less than $O˜(D δ)$ operations in K, where δ is the valuation of the resultant of F and its partial derivative with respect to Y. To this aim, we use a divide and conquer strategy and replace univariate factorisation by dynamic evaluation. As a first main corollary, we compute the irreducible factors of F in $K[[X]][Y ]$ up to an arbitrary precision X N with $O˜(D(δ + N))$ arithmetic operations. As a second main corollary, we compute the genus of the plane curve defined by F with $O˜(D^3)$ arithmetic operations and, if K = Q, with $O˜((h+1) D^3)$ bit operations using probabilistic algorithms, where h is the logarithmic height of F .
Complete list of metadata

https://hal.inria.fr/hal-01578214
Contributor : Adrien Poteaux Connect in order to contact the contributor
Submitted on : Monday, December 3, 2018 - 3:34:32 PM
Last modification on : Friday, April 1, 2022 - 3:46:20 AM

File

puiseuxd3.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution - NonCommercial - ShareAlike 4.0 International License

Identifiers

Citation

Adrien Poteaux, Martin Weimann. Computing Puiseux series: a fast divide and conquer algorithm. Annales Henri Lebesgue, UFR de Mathématiques - IRMAR, 2021, 4, pp.1061--1102. ⟨10.5802/ahl.97⟩. ⟨hal-01578214v3⟩

Share

Metrics

Record views

500

Files downloads

576