A fast algorithm for reversion of power series

Details A fast algorithm for reversion of power series A fast algorithm for reversion of power series

2011-08-24

arxiv.org/abs/1108.4772v1

Computer Science

Symbolic Computation

Scientific paper

We give an algorithm for reversion of formal power series, based on an efficient way to evaluate 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 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.

Affiliated with

Also associated with

No associations

Rating

A fast algorithm for reversion of power series does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A fast algorithm for reversion of power series, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A fast algorithm for reversion of power series will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-377353