zbMATH — the first resource for mathematics

Inverting polynomials and formal power series. (English) Zbl 0797.12008
Author’s abstract: The problem of inverting a general polynomial of degree \(d\) greater than 0, the inverse being a formal power series with coefficients \(z_ 0\), \(z_ 1,\dots\), is considered. It is shown that computing \(z_ 0\), \(z_ 1,\dots\), can be carried out in \(n+(2d-1) [\log_ 2 n]+2\) nonscalar operations over any infinite field. A lower bound of \(n+1\) for all fields follows from standard linear-independence arguments.
For fields of characteristic 0, it is also shown that computing \(z_{n+1}, \dots, z_{n+s}\) for \(n \geq 0\), \(s\geq 1\), requires at least \(s+ \min (n+1,d)/2-1\) nonscalar operations. For the case of inverting a general power series a corresponding lower bound of \(s+(n+1)/2-1\) exists. In particular, computing the \(n\)th coefficient of the inverse of a general formal power series requires at least \(n/2\) nonscalar operations.
Reviewer: J.Liang (Tampa)

12Y05 Computational aspects of field theory and polynomials (MSC2010)
68W10 Parallel algorithms in computer science
68Q25 Analysis of algorithms and problem complexity
68W30 Symbolic computation and algebraic computation
Full Text: DOI