Author: Fredrik Johansson
To appear in Mathematics of Computation.
arXiv preprint: http://arxiv.org/abs/1108.4772, published August 24, 2011; revised November 30, 2013.
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.
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