On the complexity of solving ordinary differential equations in terms of Puiseux series

2007/05/15 by Ali Ayad, Ayad, Ali
Computer Science · Mathematics · #Coding theory and cryptography #Cryptography and Residue Arithmetic #FOS: Mathematics #General Mathematics (math.GM) #Polynomial and algebraic computation #math.GM

paper · pdf · doi:10.48550/arxiv.0705.2127

arxiv created 2007/05/15 · openalex publication_date 2007/05/15 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove that the binary complexity of solving ordinary polynomial differential equations in terms of Puiseux series is single exponential in the number of terms in the series. Such a bound was given by Grigoriev [10] for Riccatti differential polynomials associated to ordinary linear differential operators. In this paper, we get the same bound for arbitrary differential polynomials. The algorithm is based on a differential version of the Newton-Puiseux procedure for algebraic equations.

Related

• A note on the computation of Puiseux series solutions of the Riccatti equation associated with a homogeneous linear ordinary differential equation
• Complexity of Puiseux solutions of differential and q-difference equations of order and degree one
• Puiseux Series and Algebraic Solutions of First Order Autonomous AODEs -- A MAPLE Package
• Computational complexity of solving polynomial differential equations over unbounded domains with non-rational coefficients
• The Newton-Puiseux algorithm and effective algebraic series