Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

A fast algorithm for reversion of power series
HTML articles powered by AMS MathViewer

by Fredrik Johansson PDF
Math. Comp. 84 (2015), 475-484 Request permission

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
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
  • MR Author ID: 999321
  • Email: fredrik.johansson@risc.jku.at
  • 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.
  • © Copyright 2014 American Mathematical Society
    The copyright for this article reverts to public domain 28 years after publication.
  • Journal: Math. Comp. 84 (2015), 475-484
  • MSC (2010): Primary 68W30
  • DOI: https://doi.org/10.1090/S0025-5718-2014-02857-3
  • MathSciNet review: 3266971