REVIEW 1 cited by
A fast algorithm for reversion of power series
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
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.
Forward citations
Cited by 1 Pith paper
-
Corecursive Coding of High Computational Derivatives and Power Series
A Haskell tutorial for deriving infinite derivative chains and power series through lazy corecursion, including composition, reversion, and a Stirling-series example.
Discussion (0). Continue with ORCID to comment.