RISC RISC Research Institute for Symbolic Computation  
  • @misc{RISC4515,
    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}