Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

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


Authors: Alin Bostan, Guillaume Chèze, Thomas Cluzeau and Jacques-Arthur Weil
Journal: Math. Comp. 85 (2016), 1393-1425
MSC (2010): Primary 34A05, 68W30, 68W40
DOI: https://doi.org/10.1090/mcom/3007
Published electronically: August 3, 2015
MathSciNet review: 3454369
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 34A05, 68W30, 68W40

Retrieve articles in all journals with MSC (2010): 34A05, 68W30, 68W40


Additional Information

Alin Bostan
Affiliation: INRIA Saclay Île-de-France, Bâtiment Alan Turing, 1 rue Honoré d’Estienne d’Orves, 91120 Palaiseau, France
Email: alin.bostan@inria.fr

Guillaume Chèze
Affiliation: Institut de Mathématiques de Toulouse, Université Paul Sabatier Toulouse 3, MIP Bât. 1R3, 31 062 TOULOUSE cedex 9, France
Email: guillaume.cheze@math.univ-toulouse.fr

Thomas Cluzeau
Affiliation: Université de Limoges; CNRS; XLIM UMR 7252; DMI, 123 avenue Albert Thomas, 87 060 LIMOGES cedex, France
Email: cluzeau@ensil.unilim.fr

Jacques-Arthur Weil
Affiliation: Université de Limoges; CNRS; XLIM UMR 7252; DMI, 123 avenue Albert Thomas, 87 060 LIMOGES cedex, France
Email: jacques-arthur.weil@unilim.fr

DOI: https://doi.org/10.1090/mcom/3007
Received by editor(s): October 9, 2013
Received by editor(s) in revised form: May 2, 2014, and October 22, 2014
Published electronically: August 3, 2015
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society