Fast Computation of the Roots of Polynomials Over the Ring of Power Series

Abstract : We give an algorithm for computing all roots of polynomials over a univariate power series ring over an exact field $\mathbb{K}$. More precisely, given a precision $d$, and a polynomial $Q$ whose coefficients are power series in $x$, the algorithm computes a representation of all power series $f(x)$ such that $Q(f(x)) = 0 \bmod x^d$. The algorithm works unconditionally, in particular also with multiple roots, where Newton iteration fails. Our main motivation comes from coding theory where instances of this problem arise and multiple roots must be handled. The cost bound for our algorithm matches the worst-case input and output size $d \deg(Q)$, up to logarithmic factors. This improves upon previous algorithms which were quadratic in at least one of $d$ and $\deg(Q)$. Our algorithm is a refinement of a divide \& conquer algorithm by Alekhnovich (2005), where the cost of recursive steps is better controlled via the computation of a factor of $Q$ which has a smaller degree while preserving the roots.
Type de document :
Communication dans un congrès
ISSAC '17, Jul 2017, Kaiserslautern, Germany. ISSAC '17, 〈http://www.issac-conference.org/2017/〉. 〈10.1145/3087604.3087642〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01457954
Contributeur : Vincent Neiger <>
Soumis le : vendredi 2 juin 2017 - 13:12:42
Dernière modification le : samedi 10 juin 2017 - 01:06:12
Document(s) archivé(s) le : mercredi 13 décembre 2017 - 09:11:04

Fichier

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

Identifiants

Collections

Citation

Vincent Neiger, Johan Rosenkilde, Éric Schost. Fast Computation of the Roots of Polynomials Over the Ring of Power Series. ISSAC '17, Jul 2017, Kaiserslautern, Germany. ISSAC '17, 〈http://www.issac-conference.org/2017/〉. 〈10.1145/3087604.3087642〉. 〈hal-01457954v2〉

Partager

Métriques

Consultations de la notice

82

Téléchargements de fichiers

57