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?)

  • [1] Shreeram S. Abhyankar, William J. Heinzer, and Avinash Sathaye, Translates of polynomials, A tribute to C. S. Seshadri (Chennai, 2002) Trends Math., Birkhäuser, Basel, 2003, pp. 51-124. MR 2017580 (2004k:12002)
  • [2] J. M. Aroca, J. Cano, R. Feng, and X. S. Gao, Algebraic general solutions of algebraic ordinary differential equations, ISSAC'05, ACM, New York, 2005, pp. 29-36 (electronic). MR 2280526, https://doi.org/10.1145/1073884.1073891
  • [3] Bernhard Beckermann and George Labahn, A uniform approach for the fast computation of matrix-type Padé approximants, SIAM J. Matrix Anal. Appl. 15 (1994), no. 3, 804-823. MR 1282696 (95f:65030), https://doi.org/10.1137/S0895479892230031
  • [4] Dario Bini and Victor Y. Pan, Polynomial and Matrix Computations. Vol. 1, Progress in Theoretical Computer Science, Birkhäuser Boston, Inc., Boston, MA, 1994. Fundamental algorithms. MR 1289412 (95k:65003)
  • [5] Arnaud Bodin, Reducibility of rational functions in several variables, Israel J. Math. 164 (2008), 333-347. MR 2391153 (2009a:12004), https://doi.org/10.1007/s11856-008-0033-2
  • [6] A. Bostan, F. Chyzak, F. Ollivier, B. Salvy, É. Schost, and A. Sedoglavic, Fast computation of power series solutions of systems of differential equations, Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, 2007, pp. 1012-1021. MR 2485252
  • [7] A. Bostan, G. Lecerf, B. Salvy, É. Schost, and B. Wiebelt, Complexity issues in bivariate polynomial factorization, ISSAC 2004, ACM, New York, 2004, pp. 42-49. MR 2126923 (2005k:68084), https://doi.org/10.1145/1005285.1005294
  • [8] Alin Bostan, Frédéric Chyzak, Bruno Salvy, Grégoire Lecerf, and Éric Schost, Differential equations for algebraic functions, ISSAC 2007, ACM, New York, 2007, pp. 25-32. MR 2396180 (2009e:68122), https://doi.org/10.1145/1277548.1277553
  • [9] R. P. Brent and H. T. Kung, Fast algorithms for manipulating formal power series, J. Assoc. Comput. Mach. 25 (1978), no. 4, 581-595. MR 0520733 (58 #25090)
  • [10] L. Busé and G. Chèze, On the total order of reducibility of a pencil of algebraic plane curves, J. Algebra 341 (2011), 256-278. MR 2824521, https://doi.org/10.1016/j.jalgebra.2011.06.006
  • [11] Laurent Busé, Guillaume Chèze, and Salah Najib, Noether forms for the study of non-composite rational functions and their spectrum, Acta Arith. 147 (2011), no. 3, 217-231. MR 2773201 (2012c:12001), https://doi.org/10.4064/aa147-3-2
  • [12] Manuel M. Carnicer, The Poincaré problem in the nondicritical case, Ann. of Math. (2) 140 (1994), no. 2, 289-294. MR 1298714 (95k:32031), https://doi.org/10.2307/2118601
  • [13] D. Cerveau and A. Lins Neto, Holomorphic foliations in $ {\bf C}{\rm P}(2)$ having an invariant algebraic curve, Ann. Inst. Fourier (Grenoble) 41 (1991), no. 4, 883-903 (English, with French summary). MR 1150571 (93b:32050)
  • [14] J. Chavarriga, H. Giacomini, and M. Grau, Necessary conditions for the existence of invariant algebraic curves for planar polynomial systems, Bull. Sci. Math. 129 (2005), no. 2, 99-126 (English, with English and French summaries). MR 2123262 (2005k:34123), https://doi.org/10.1016/j.bulsci.2004.09.002
  • [15] Javier Chavarriga and Isaac A. García, The Poincaré problem in the non-resonant case: an algebraic approach, Differ. Geom. Dyn. Syst. 8 (2006), 54-68 (electronic). MR 2220709 (2007m:34075)
  • [16] Javier Chavarriga, Hector Giacomini, Jaume Giné, and Jaume Llibre, Darboux integrability and the inverse integrating factor, J. Differential Equations 194 (2003), no. 1, 116-139. MR 2001031 (2004e:34001), https://doi.org/10.1016/S0022-0396(03)00190-6
  • [17] Guillaume Chèze, Computation of Darboux polynomials and rational first integrals with bounded degree in polynomial time, J. Complexity 27 (2011), no. 2, 246-262. MR 2776495 (2012k:65182), https://doi.org/10.1016/j.jco.2010.10.004
  • [18] Guillaume Chèze, Bounding the number of remarkable values via Jouanolou's theorem, J. Differential Equations 258 (2015), no. 10, 3535-3545. MR 3319428, https://doi.org/10.1016/j.jde.2015.01.027
  • [19] Guillaume Chèze, A recombination algorithm for the decomposition of multivariate rational functions, Math. Comp. 82 (2013), no. 283, 1793-1812. MR 3042585, https://doi.org/10.1090/S0025-5718-2012-02658-5
  • [20] Bartomeu Coll, Antoni Ferragut, and Jaume Llibre, Polynomial inverse integrating factors for quadratic differential systems, Nonlinear Anal. 73 (2010), no. 4, 881-914. MR 2653758 (2011k:34099), https://doi.org/10.1016/j.na.2010.04.004
  • [21] S. C. Coutinho and L. Menasché Schechter, Algebraic solutions of holomorphic foliations: an algorithmic approach, J. Symbolic Comput. 41 (2006), no. 5, 603-618. MR 2209167 (2007b:32050), https://doi.org/10.1016/j.jsc.2005.11.002
  • [22] S. C. Coutinho and L. Menasché Schechter, Algebraic solutions of plane vector fields, J. Pure Appl. Algebra 213 (2009), no. 1, 144-153. MR 2462992 (2009k:32023), https://doi.org/10.1016/j.jpaa.2008.06.003
  • [23] Gaston Darboux, Mémoire sur les équations différentielles du premier ordre et du premier degré, Bull. Sci. Math. 32 (1878), 60-96, 123-144, 151-200.
  • [24] L. G. S. Duarte, S. E. S. Duarte, L. A. C. P. da Mota, and J. E. F. Skea, Solving second-order ordinary differential equations by extending the Prelle-Singer method, J. Phys. A 34 (2001), no. 14, 3015-3024. MR 1832368 (2002b:34003), https://doi.org/10.1088/0305-4470/34/14/308
  • [25] Freddy Dumortier, Jaume Llibre, and Joan C. Artés, Qualitative Theory of Planar Differential Systems, Universitext, Springer-Verlag, Berlin, 2006. MR 2256001 (2007f:34001)
  • [26] Antoni Ferragut and Héctor Giacomini, A new algorithm for finding rational first integrals of polynomial vector fields, Qual. Theory Dyn. Syst. 9 (2010), no. 1-2, 89-99. MR 2737363 (2011k:34076), https://doi.org/10.1007/s12346-010-0021-x
  • [27] Antoni Ferragut and Jaume Llibre, On the remarkable values of the rational first integrals of polynomial vector fields, J. Differential Equations 241 (2007), no. 2, 399-417. MR 2358899 (2009f:34076), https://doi.org/10.1016/j.jde.2007.05.002
  • [28] Joachim von zur Gathen and Jürgen Gerhard, Modern Computer Algebra, Cambridge University Press, New York, 1999. MR 1689167 (2000j:68205)
  • [29] Jaume Giné and Jaume Llibre, On the integrable rational Abel differential equations, Z. Angew. Math. Phys. 61 (2010), no. 1, 33-39. MR 2600253 (2011b:34102), https://doi.org/10.1007/s00033-009-0013-3
  • [30] Alain Goriely, Integrability and Nonintegrability of Dynamical Systems, Advanced Series in Nonlinear Dynamics, vol. 19, World Scientific Publishing Co., Inc., River Edge, NJ, 2001. MR 1857742 (2002k:37001)
  • [31] Jaime Gutierrez, Rosario Rubio, and David Sevilla, On multivariate rational function decomposition, J. Symbolic Comput. 33 (2002), no. 5, 545-562. Computer algebra (London, ON, 2001). MR 1919903 (2003f:12008), https://doi.org/10.1006/jsco.2000.0529
  • [32] J. P. Jouanolou, Équations de Pfaff algébriques, Lecture Notes in Mathematics, vol. 708, Springer, Berlin, 1979 (French). MR 537038 (81k:14008)
  • [33] Erich Kaltofen, Polynomial-time reductions from multivariate to bi- and univariate integral polynomial factorization, SIAM J. Comput. 14 (1985), no. 2, 469-489. MR 784750 (86j:12001), https://doi.org/10.1137/0214035
  • [34] Grégoire Lecerf, Sharp precision in Hensel lifting for bivariate polynomial factorization, Math. Comp. 75 (2006), no. 254, 921-933 (electronic). MR 2197000 (2007g:12008), https://doi.org/10.1090/S0025-5718-06-01810-2
  • [35] Jinzhi Lei and Lijun Yang, Algebraic multiplicity and the Poincaré problem, Differential equations with symbolic computation, Trends Math., Birkhäuser, Basel, 2005, pp. 143-157. MR 2187378 (2006m:34004), https://doi.org/10.1007/3-7643-7429-2_9
  • [36] Jaume Llibre and Xiang Zhang, Rational first integrals in the Darboux theory of integrability in $ \mathbb{C}^n$, Bull. Sci. Math. 134 (2010), no. 2, 189-195. MR 2592968 (2011b:37090), https://doi.org/10.1016/j.bulsci.2007.12.001
  • [37] Dino Lorenzini, Reducibility of polynomials in two variables, J. Algebra 156 (1993), no. 1, 65-75. MR 1213785 (94b:14006), https://doi.org/10.1006/jabr.1993.1063
  • [38] Yiu-Kwong Man and Malcolm A. H. MacCallum, A rational approach to the Prelle-Singer algorithm, J. Symbolic Comput. 24 (1997), no. 1, 31-43. MR 1459668 (98g:12009), https://doi.org/10.1006/jsco.1997.0111
  • [39] Jean Moulin Ollagnier, Algebraic closure of a rational function, Qual. Theory Dyn. Syst. 5 (2004), no. 2, 285-300. MR 2275442 (2007h:13035), https://doi.org/10.1007/BF02972683
  • [40] Peter J. Olver, Applications of Lie groups to differential equations, 2nd ed., Graduate Texts in Mathematics, vol. 107, Springer-Verlag, New York, 1993. MR 1240056 (94g:58260)
  • [41] Jorge Vitório Pereira, Vector fields, invariant varieties and linear systems, Ann. Inst. Fourier (Grenoble) 51 (2001), no. 5, 1385-1405 (English, with English and French summaries). MR 1860669 (2003e:32041)
  • [42] Jorge Vitório Pereira, On the Poincaré problem for foliations of general type, Math. Ann. 323 (2002), no. 2, 217-226. MR 1913040 (2003e:32056), https://doi.org/10.1007/s002080100277
  • [43] H. Poincaré, Sur l'intégration algébrique des équations différentielles du premier ordre et du premier degré, Rend. Circ. Mat. Palermo 5 (1891), 161-191.
  • [44] M. J. Prelle and M. F. Singer, Elementary first integrals of differential equations, Trans. Amer. Math. Soc. 279 (1983), no. 1, 215-229. MR 704611 (85d:12008), https://doi.org/10.2307/1999380
  • [45] Wolfgang Ruppert, Reduzibilität ebener Kurven, J. Reine Angew. Math. 369 (1986), 167-191 (German). MR 850633 (88j:14010), https://doi.org/10.1515/crll.1986.369.167
  • [46] B. Salvy and P. Zimmermann, GFUN: a Maple package for the manipulation of generating and holonomic functions in one variable, 20 (1994), no. 2, 163-167.
  • [47] A. Schinzel, Polynomials with special regard to reducibility, Encyclopedia of Mathematics and its Applications, vol. 77, Cambridge University Press, Cambridge, 2000. With an appendix by Umberto Zannier. MR 1770638 (2001h:11135)
  • [48] Dana Schlomiuk, Elementary first integrals and algebraic invariant curves of differential equations, Exposition. Math. 11 (1993), no. 5, 433-454. MR 1249165 (95a:34043)
  • [49] Dana Schlomiuk, John Guckenheimer, and Richard Rand, Integrability of plane quadratic vector fields, Exposition. Math. 8 (1990), no. 1, 3-25. MR 1042200 (91b:58200)
  • [50] R. E. Shafer, On quadratic approximation, SIAM J. Numer. Anal. 11 (1974), 447-460. MR 0358161 (50 #10626)
  • [51] Robert E. Shafer, On quadratic approximation. II, Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. Fiz. 602-633 (1978), 163-170 (1979). MR 580440 (81m:41011)
  • [52] Michael F. Singer, Liouvillian first integrals of differential equations, Trans. Amer. Math. Soc. 333 (1992), no. 2, 673-688. MR 1062869 (92m:12014), https://doi.org/10.2307/2154053
  • [53] M. van Hoeij and J.-A. Weil, Solving second order linear differential equations with Klein's theorem, ISSAC'05, ACM, New York, 2005, pp. 340-347. MR 2280566, https://doi.org/10.1145/1073884.1073931
  • [54] Angelo Vistoli, Erratum: ``The number of reducible hypersurfaces in a pencil'', Invent. Math. 113 (1993), no. 2, 445. MR 1228133 (94d:14008b), https://doi.org/10.1007/BF01244314
  • [55] Angelo Vistoli, The number of reducible hypersurfaces in a pencil, Invent. Math. 112 (1993), no. 2, 247-262. MR 1213102 (94d:14008a), https://doi.org/10.1007/BF01232434
  • [56] Sebastian Walcher, On the Poincaré problem, J. Differential Equations 166 (2000), no. 1, 51-78. MR 1779255 (2001m:32067), https://doi.org/10.1006/jdeq.2000.3801
  • [57] J.-A. Weil, Constantes et polynômes de Darboux en algèbre différentielle : applications aux systèmes différentiels linéaires, Ph.D. thesis, École polytechnique, 1995.

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