@

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}