Faster algorithms for the square root and reciprocal of power series

Abstract:

We give new algorithms for the computation of square roots and reciprocals of power series in $\mathbf {C}\lBrack x \rBrack$. If $M(n)$ denotes the cost of multiplying polynomials of degree $n$, the square root to order $n$ costs $(1.333\ldots + o(1)) M(n)$ and the reciprocal costs $(1.444\ldots + o(1)) M(n)$. These improve on the previous best results, $(1.8333\ldots + o(1)) M(n)$ and $(1.5 + o(1)) M(n)$, respectively.