Computing power series solutions of a nonlinear PDE system

ABSTRACT

This paper presents a new algorithm to compute the power series solutions of a significant class of nonlinear systems of partial differential equations. The algorithm is very different from previous algorithms to perform this task. Those relie on differentiating iteratively the differential equations to get coefficients of the power series, one at a time. The algorithm presented here relies on using the linearisation of the system and the associated recurrences. At each step the order up to which the power series solution is known is doubled. The algorithm can be seen as belonging to the family of Newton iteration methods.

REFERENCES

• 1: F. Boulier and E. Hubert. phdiffalg: description, help pages and examples of use. Symbolic Computation Group, University of Waterloo, Ontario, Canada, 1998. Now available at http://www.inria.fr/cafe/Evelyne.Hubert/webdiffalg.
• 2: F. Boulier , D. Lazard , F. Ollivier , M. Petitot, Representation for the radical of a finitely generated differential ideal, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.158-166, July 10-12, 1995, Montreal, Quebec, Canada [doi>10.1145/220346.220367]
• 3: F. Boulier, D. Lazard, F. Ollivier, and M. Petitot. Computing representations for radicals of finitely generated differential ideals. Technical Report IT-306, LIFL, 1997.
• 4: Driss Bouziane , Abdelilah Kandri Rody , Hamid Maârouf, Unmixed-dimensional decomposition of a finitely generated perfect differential ideal, Journal of Symbolic Computation, v.31 n.6, p.631-649, June 2001 [doi>10.1006/jsco.1999.1562]
• 5: R. P. Brent , H. T. Kung, Fast Algorithms for Manipulating Formal Power Series, Journal of the ACM (JACM), v.25 n.4, p.581-595, Oct. 1978 [doi>10.1145/322092.322099]
• 6: G. Carra Ferro. Gröbner bases and differential algebra. In AAECC, volume 356 of Lecture Notes in Computer Science. Springer-Verlag Berlin, 1987.
• 7: J. Denef and L. Lipshitz. Power series solutions of algebraic differential equations. Mathematische Annalen, 267(2):213--238, 1984.
• 8: Keith O. Geddes, Convergence behavior of the Newton iteration for first order differential equations, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.189-199, June 01, 1979
• 9: L. Guo, W. F. Keigher, P. J. Cassidy, and W. Y. Sit, editors. Differential Algebra and Related Topics. World Scientific Publishing Co., 2002.
• 10: Evelyne Hubert, Factorization-free decomposition algorithms in differential algebra, Journal of Symbolic Computation, v.29 n.4-5, p.641-662, April/May 2000 [doi>10.1006/jsco.1999.0344]
• 11: E. Hubert. Notes on triangular sets and triangulation-decomposition algorithms I: Polynomial systems. In F.Winkler and U.Langer, editors, Symbolic and Numerical Scientific Computations, LNCS. Springer, to appear.
• 12: E. Hubert. Notes on triangular sets and triangulation-decomposition algorithms II: Differential systems. In F.Winkler and U.Langer, editors, Symbolic and Numerical Scientific Computating, LNCS. Springer, to appear.
• 13: E. Kolchin. Selected works of Ellis Kolchin with commentary. Commentaries by Armand Borel, Michael F. Singer, Bruno Poizat, Alexandru Buium and Phyllis J. Cassidy, Edited and with a preface by Hyman Bass, Buium and Cassidy. American Mathematical Society, Providence, RI, 1999.
• 14: E. R. Kolchin. Differential Algebra and Algebraic Groups, volume 54 of Pure and Applied Mathematics. Academic Press, New York-London, 1973.
• 15: F. Lemaire. Contribution à l'algorithmique en algèbre différentielle. PhD thesis, Université des Sciences et Technologies de Lille, 2002.
• 16: F. Lemaire. Les classements les plus généraux assurant l'analycité des solutions des systèmes orthonomes pour des conditions initiales analytiques. In CASC. Technische Universität München, 2002.
• 17: E. L. Mansfield. Differential Gröbner Bases. PhD thesis, University of Sydney, 1991.
• 18: François Ollivier, Standard Bases of Differential Ideals, Proceedings of the 8th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.304-321, August 20-24, 1990
• 19: A. Peladan-Germa. Testing equality in differential ring extensions defined by pde's and limit conditions. Applicable Algebra in Engineering, Communication and Computing, 13(4):257--288, 2002.
• 20: G. J. Reid, A. D. Wittkopf, and A. Boulton. Reduction of systems of nonlinear partial differential equations to simplified involutive forms. Eur. J. of Appl. Math., 7:604 -- 635, 1996.
• 21: C. Riquier. Les systèmes d'équations aux dérivées partielles. Gauthier-Villars, Paris, 1910.
• 22: J. F. Ritt. Differential Algebra, volume XXXIII of Colloquium publications. American Mathematical Society, 1950. http://www.ams.org/online_bks.
• 23: A. Rosenfeld. Specializations in differential algebra. Transaction of the American Mathematical Society, 90:394--407, 1959.
• 24: C. J. Rust , G. J. Reid , A. D. Wittkopf, Existence and uniqueness theorems for formal power series solutions of analytic differential systems, Proceedings of the 1999 international symposium on Symbolic and algebraic computation, p.105-112, July 28-31, 1999, Vancouver, British Columbia, Canada [doi>10.1145/309831.309875]
• 25: Alexandre Sedoglavic, A probabilistic algorithm to test local algebraic observability in polynomial time, Proceedings of the 2001 international symposium on Symbolic and algebraic computation, p.309-317, July 2001, London, Ontario, Canada [doi>10.1145/384101.384143]
• 26: A. Seidenberg. Abstract differential algebra and the analytic case. Proceedings of the American Mathematical Society, 9:159--164, 1958.
• 27: W. Sit. The Ritt-Kolchin theory for differential polynomials. In Guo et al. {9}.
• 28: Joris Van der Hoeven, Relax, but don't be too lazy, Journal of Symbolic Computation, v.34 n.6, p.479-542, December 2002 [doi>10.1006/jsco.2002.0562]
• 29: A. Witkopf and G. Reid. The RIF package. CECM - Simon Fraser University - Vancouver, http://www.cecm.sfu.ca/ wittkopf/rif.html.
• 30: W. T. Wu. On the foundation of algebraic differential geometry. Systems Science and Mathematical Sciences, 2(4):289--312, 1989.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms

Additional Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS

General Terms:
Algorithms

Keywords:
Newton iteration, differential algebra, formal integrability, nonlinear partial differential systems, power series solutions