# A fast algorithm for reversion of power series

Author: Fredrik Johansson

Final submitted version (PDF)

To appear in Mathematics of Computation.

arXiv preprint: http://arxiv.org/abs/1108.4772, published August 24, 2011; revised November 30, 2013.

## Abstract

We give an algorithm for reversion of formal power series, based on an efficient way to implement the Lagrange inversion formula. Our algorithm requires $O(n^{1/2}(M(n) + M\!M(n^{1/2})))$ operations where $M(n)$ and $M\!M(n)$ are the costs of polynomial and matrix multiplication respectively. This matches the asymptotic complexity of 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.

## Implementation

This algorithm is implemented in FLINT which uses it by default for reversion of power series over $\mathbb{Z}$, $\mathbb{Q}$ and $\mathbb{Z}/n\mathbb{Z}$. As reported in the paper, it is usually faster in practice than previously known algorithms, including Horner's rule and the first Brent-Kung algorithm (both available in FLINT) as well as the second Brent-Kung algorithm which in theory should be asymptotically faster. The second Brent-Kung algorithm is currently not available in FLINT since it is complicated to implement with a similar level of optimization as the other algorithm, and in any case not faster (I have privately implemented an experimental version over $\mathbb{Z}/n\mathbb{Z}$ just for benchmarking purposes).

The algorithm is now also used in Arb for reversion of power series with ball coefficients over $\mathbb{R}$ and $\mathbb{C}$. Initial experiments indicate that its numerical stability typically is much better than Horner's rule and slightly better than the first Brent-Kung algorithm, with speed similar or slightly better than the latter.

Last updated July 31, 2014. Contact: fredrik.johansson@gmail.com.

Back to fredrikj.net