A fast algorithm for reversion of power series

DOI10.1090/S0025-5718-2014-02857-3MaRDI QIDQ5497035zbMATH OpenFDO

Authors Fredrik Johansson

Publication date 30 January 2015

Published in Mathematics of Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1108.4772

zbMATH Keywords

reversion of formal power series

Mathematics Subject Classification ID

Software, source code, etc. for problems pertaining to functions of a complex variable (30-04) Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

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)+MM(n^{1/2})))$ operations where $M(n)$ and $MM(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.

Recommendations

• Fast algorithms for elementary operations on complex power series
• Faster algorithms for the square root and reciprocal of power series
• Fast Lagrange inversion, with an application to factorial numbers
• Inverting Polynomials and Formal Power Series
• Relax, but don't be too lazy

Cites work

• A fast numerical algorithm for the composition of power series with complex coefficients
• Composing power series over a finite ring in essentially linear time
• Duality Applied to the Complexity of Matrix Multiplication and Other Bilinear Forms
• Fast Algorithms for Manipulating Formal Power Series
• Fast Library for Number Theory: An Introduction
• Fast multiplication and its applications
• Fast polynomial factorization and modular composition
• Fast rectangular matrix multiplication and applications
• Faster algorithms for the square root and reciprocal of power series
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• scientific article; zbMATH DE number 1936673 (Why is no real title available?)
• On the Additive Complexity of Matrix Multiplication
• Power series composition and change of basis
• Relax, but don't be too lazy

Cited in

(17)

• A fast numerical algorithm for the composition of power series with complex coefficients
• Fast Lagrange inversion, with an application to factorial numbers
• Relax, but don't be too lazy
• The middle product algorithm. I: Speeding up the division and square root of power series
• An FFT-based algorithm for \(2\)D power series expansions
• Fast multivariate multi-point evaluation revisited
• Faster algorithms for the square root and reciprocal of power series
• scientific article; zbMATH DE number 4201452 (Why is no real title available?)
• Fast algorithms for elementary operations on complex power series
• Inverting Polynomials and Formal Power Series
• Power series composition and change of basis
• Highest cusped waves for the Burgers-Hilbert equation
• On the computation of modular forms on noncongruence subgroups
• Highest cusped waves for the fractional KdV equations
• Modular composition via factorization
• Newton's method and FFT trading
• A simple and fast algorithm for computing exponentials of power series

Describes a project that uses

Uses Software

• FLINT
• MPIR

This page was built for publication: A fast algorithm for reversion of power series

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5497035)