Projects per year
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 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 worstcase 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 language  English 

Title of host publication  ISSAC 2017  Proceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation 
Number of pages  8 
Volume  Part F129312 
Publisher  Association for Computing Machinery 
Publication date  23 Jul 2017 
Pages  349356 
ISBN (Electronic)  9781450350648 
DOIs  
Publication status  Published  23 Jul 2017 
Event  42nd ACM International Symposium on Symbolic and Algebraic Computation, ISSAC 2017  University of Kaiserslautern, Kaiserslautern, Germany Duration: 25 Jul 2017 → 28 Jul 2017 Conference number: 42 
Conference
Conference  42nd ACM International Symposium on Symbolic and Algebraic Computation, ISSAC 2017 

Number  42 
Location  University of Kaiserslautern 
Country  Germany 
City  Kaiserslautern 
Period  25/07/2017 → 28/07/2017 
Sponsor  Association for Computing Machinery 
Keywords
 List decoding
 Polynomial rootfinding algorithm
 Power series
Fingerprint
Dive into the research topics of 'Fast computation of the roots of polynomials over the ring of power series'. Together they form a unique fingerprint.Projects
 1 Finished

COFUNDPostdocDTU: COFUNDPostdocDTU
Præstrud, M. R. & Brodersen, S. W.
01/01/2014 → 31/12/2019
Project: Research