A dichotomic Newton-Puiseux algorithm using dynamic evaluation

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 rational Puiseux expansions 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 factorization 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˜(hD 3) bit operations where h is the logarithmic heigth of F .
Keywords : Puiseux series
Type de document :
Pré-publication, Document de travail
2017
Liste complète des métadonnées

Littérature citée [33 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01578214
Contributeur : Adrien Poteaux <>
Soumis le : mercredi 3 janvier 2018 - 23:21:51
Dernière modification le : mercredi 25 avril 2018 - 15:44:22

Fichier

puiseuxd3.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité - Pas d'utilisation commerciale - Partage selon les Conditions Initiales 4.0 International License

Identifiants

  • HAL Id : hal-01578214, version 2

Citation

Adrien Poteaux, Martin Weimann. A dichotomic Newton-Puiseux algorithm using dynamic evaluation. 2017. 〈hal-01578214v2〉

Partager

Métriques

Consultations de la notice

127

Téléchargements de fichiers

23