# Inverting Polynomials and Formal Power Series

K. Kalorkoti

Research output: Contribution to journalArticlepeer-review

## Abstract

The problem of inverting a general polynomial of degree \$d > 0\$, the inverse being a formal power series with coefficients \$z_0 ,z_1 ,z_2 , \ldots \$ is considered. It is shown that computing \$z_0 , \ldots ,z_n \$ can be carried out in \$n + (2d - 1)\lceil {\log _2 n} \rceil + 2\$ nonscalar operations over any infinite field. A lower bound of \$n + 1\$ for all fields follows from standard linear-independence arguments. (The model of computation consists of straight-line algorithms.)

For fields of characteristic 0, it is also shown that computing \$z_{n + 1} , \ldots ,z_{n + s} \$ for \$n \geqslant 0\$, \$s \geqslant 1\$, requires at least \$s + \min {{(n + 1,d)} / {2 - 1}}\$ nonscalar operations. For the case of inverting a general formal power series a corresponding lower bound of \$s + {{(n + 1)} / {2 - 1}}\$ exists. In particular, computing the nth coefficient of the inverse of a general formal power series requires at least \${n / 2}\$ nonscalar operations (the coefficients are numbered from zero).
Original language English 552-559 8 SIAM Journal on Computing 22 3 https://doi.org/10.1137/0222037 Published - Jun 1993

## Fingerprint

Dive into the research topics of 'Inverting Polynomials and Formal Power Series'. Together they form a unique fingerprint.