Efficient algorithms for computing rational first integrals and Darboux polynomials of planar polynomial vector fields

Abstract:

We present fast algorithms for computing rational first integrals with bounded degree of a planar polynomial vector field. Our approach builds upon a method proposed by Ferragut and Giacomini, whose main ingredients are the calculation of a power series solution of a first order differential equation and the reconstruction of a bivariate polynomial annihilating this power series. We provide explicit bounds on the number of terms needed in the power series. This enables us to transform their method into a certified algorithm computing rational first integrals via systems of linear equations. We then significantly improve upon this first algorithm by building a probabilistic algorithm with arithmetic complexity $\tilde {\mathcal {O}}(N^{2 \omega })$ and a deterministic algorithm solving the problem in at most $\tilde {\mathcal {O}}(N^{2 \omega +1})$ arithmetic operations, where $N$ denotes the given bound for the degree of the rational first integral, and $\omega$ the exponent of linear algebra. We also provide a fast heuristic variant which computes a rational first integral, or fails, in $\tilde {\mathcal {O}}(N^{\omega +2})$ arithmetic operations. By comparison, the best previously known complexity was $N^{4\omega +4}$ arithmetic operations. We then show how to apply a similar method to the computation of Darboux polynomials. The algorithms are implemented in a Maple package RationalFirstIntegrals which is available to interested readers with examples showing its efficiency.