Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.98.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.


Efficient algorithms for computing rational first integrals and Darboux polynomials of planar polynomial vector fields
HTML articles powered by AMS MathViewer

by Alin Bostan, Guillaume Chèze, Thomas Cluzeau and Jacques-Arthur Weil PDF
Math. Comp. 85 (2016), 1393-1425 Request permission


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.
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
  • MR Author ID: 725685
  • Email:
  • 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:
  • Thomas Cluzeau
  • Affiliation: Université de Limoges; CNRS; XLIM UMR 7252; DMI, 123 avenue Albert Thomas, 87 060 LIMOGES cedex, France
  • Email:
  • Jacques-Arthur Weil
  • Affiliation: Université de Limoges; CNRS; XLIM UMR 7252; DMI, 123 avenue Albert Thomas, 87 060 LIMOGES cedex, France
  • Email:
  • 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
  • © Copyright 2015 American Mathematical Society
  • Journal: Math. Comp. 85 (2016), 1393-1425
  • MSC (2010): Primary 34A05, 68W30, 68W40
  • DOI:
  • MathSciNet review: 3454369