# Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.78.

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 fieldsHTML articles powered by AMS MathViewer

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

## 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
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
• 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: 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
• 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: https://doi.org/10.1090/mcom/3007
• MathSciNet review: 3454369