Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

Request Permissions   Purchase Content 
 

 

A fast algorithm for reversion of power series


Author: Fredrik Johansson
Journal: Math. Comp. 84 (2015), 475-484
MSC (2010): Primary 68W30
DOI: https://doi.org/10.1090/S0025-5718-2014-02857-3
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
Email: fredrik.johansson@risc.jku.at

DOI: https://doi.org/10.1090/S0025-5718-2014-02857-3
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.