Power Series Composition in Near-Linear Time

2024/04/08 by Yasunori Kinoshita, Kinoshita, Yasunori, Baitian Li +1
Computer Science · Engineering · #FOS: Computer and information sciences #I.1.2 #Matrix Theory and Algorithms #Power Systems and Technologies #Railway Systems and Energy Efficiency #Symbolic Computation (cs.SC)

paper · pdf · doi:10.48550/arxiv.2404.05177

openalex publication_date 2024/04/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present an algebraic algorithm that computes the composition of two power series in softly linear time complexity. The previous best algorithms are \mathop\mathrm O(n^1+o(1)) by Kedlaya and Umans (FOCS 2008) and an \mathop\mathrm O(n^1.43) algebraic algorithm by Neiger, Salvy, Schost and Villard (JACM 2023). Our algorithm builds upon the recent Graeffe iteration approach to manipulate rational power series introduced by Bostan and Mori (SOSA 2021).

Related

• A fast algorithm for reversion of power series
• FPS In Action: An Easy Way To Find Explicit Formulas For Interlaced Hypergeometric Sequences
• A note on the fast power series' exponential
• Encoding algebraic power series
• On the Order of Power Series and the Sum of Square Roots Problem