Let and be two convergent power series in or , whose first terms are given numerically with a -bit precision for a fixed constant . Assuming that , we will show in this paper that the first coefficients of can be computed with a -bit precision in time . Using Newton iteration, a similar complexity bound holds for power series reversion of . Our method relies on fast multi-point evaluation, which will be recalled and further detailed for numeric polynomials. We also discuss relaxed variants of our algorithm.

Keywords: power series, composition, FFT, multi-point evaluation, algorithm

A.M.S. subject classification: 40-04, 42-04, 68W40

View: Html, TeXmacs, Pdf, BibTeX