Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



A fast algorithm for reversion of power series

Author: Fredrik Johansson
Journal: Math. Comp. 84 (2015), 475-484
MSC (2010): Primary 68W30
Published electronically: May 6, 2014
MathSciNet review: 3266971
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 68W30

Retrieve articles in all journals with MSC (2010): 68W30

Additional Information

Fredrik Johansson
Affiliation: Research Institute for Symbolic Computation, Johannes Kepler University, 4040 Linz, Austria

Received by editor(s): August 22, 2011
Received by editor(s) in revised form: April 26, 2013
Published electronically: May 6, 2014
Additional Notes: This work was supported by Austrian Science Fund (FWF) grant Y464-N18.
Article copyright: © Copyright 2014 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society