Fast computation of the roots of polynomials over the ring of power series

Vincent Neiger, Johan Rosenkilde, Éric Schost

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

255 Downloads (Pure)

Abstract

We give an algorithm for computing all roots of polynomials over a univariate power series ring over an exact field 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 mod xd. 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.

Original languageEnglish
Title of host publicationISSAC 2017 - Proceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation
Number of pages8
VolumePart F129312
PublisherAssociation for Computing Machinery
Publication date23 Jul 2017
Pages349-356
ISBN (Electronic)9781450350648
DOIs
Publication statusPublished - 23 Jul 2017
Event42nd ACM International Symposium on Symbolic and Algebraic Computation, ISSAC 2017 - University of Kaiserslautern, Kaiserslautern, Germany
Duration: 25 Jul 201728 Jul 2017
Conference number: 42

Conference

Conference42nd ACM International Symposium on Symbolic and Algebraic Computation, ISSAC 2017
Number42
LocationUniversity of Kaiserslautern
CountryGermany
CityKaiserslautern
Period25/07/201728/07/2017
SponsorAssociation for Computing Machinery

Keywords

  • List decoding
  • Polynomial root-finding algorithm
  • Power series

Projects

COFUNDPostdocDTU: COFUNDPostdocDTU

Præstrud, M. R. & Brodersen, S. W.

01/01/201431/12/2019

Project: Research

Cite this

Neiger, V., Rosenkilde, J., & Schost, É. (2017). Fast computation of the roots of polynomials over the ring of power series. In ISSAC 2017 - Proceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation (Vol. Part F129312, pp. 349-356). Association for Computing Machinery. https://doi.org/10.1145/3087604.3087642