2011/08/24 by Fredrik Johansson, Johansson, Fredrik
Computer Science · #68W30 #Coding theory and cryptography #Complexity and Algorithms in Graphs #FOS: Computer and information sciences #Polynomial and algebraic computation #Symbolic Computation (cs.SC)
paper · pdf · doi:10.48550/arxiv.1108.4772
openalex publication_date 2011/08/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(n1/2(M(n) + MM(n1/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.