Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

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 .
Document type :
Preprints, Working Papers, ...
Complete list of metadata

https://hal.inria.fr/hal-01578214
Contributor : Adrien Poteaux <>
Submitted on : Monday, December 3, 2018 - 3:34:32 PM
Last modification on : Friday, January 8, 2021 - 3:14:02 PM

File

puiseuxd3.pdf
Files produced by the author(s)

Licence


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

Identifiers

  • HAL Id : hal-01578214, version 3

Citation

Adrien Poteaux, Martin Weimann. Computing Puiseux series: a fast divide and conquer algorithm. 2017. ⟨hal-01578214v3⟩

Share

Metrics

Record views

299

Files downloads

1373