author = {Fredrik Johansson},
title = {{A fast algorithm for reversion of power series}},
language = {english},
abstract = {We give an algorithm for reversion of formal power series, based on an efficient way to evaluate the Lagrange inversion formula. Our algorithm requires $O(n^{1/2}(\M(n) + \MM(n^{1/2})))$ operations where $\M(n)$ and $\MM(n)$ are the costs of polynomial and matrix multiplication respectively. This matches an algorithm of Brent and Kung, but we achieve a constant factor speedup whose magnitude depends on the polynomial and matrix multiplication algorithms used. Benchmarks confirm that the algorithm performs well in practice. },
year = {2011},
translation = {0},
refereed = {no},
howpublished = {arxiv preprint},
length = {0}