Improvements to a triangulation-decomposition algorithm for ordinary differential systems in higher degree cases

ABSTRACT

We introduce new ideas to improve the efficiency and rationality of a triangulation decomposition algorithm. On the one hand we identify and isolate the polynomial remainder sequences in the triangulation-decomposition algorithm. Subresultant polynomial remainder sequences are then used to compute them and their specialization properties are applied for the splittings. The gain is two fold: control of expression swell and reduction of the number of splittings. On the other hand, we remove the role that initials had in previous triangulation-decomposition algorithms. They are not needed in theoretical results and it was expected that they need not appear in the input and output of the algorithms. This is the case of the algorithm presented. New algorithms are presented to compute a subsequent characteristic decomposition from the output of the triangulation decomposition algorithm where the initials need not appear.

REFERENCES

• 1: P. Aubry. Ensembles triangulaires de polynômes et rsolution de systémes algèbriques. Implantation en Axiom. PhD thesis, Universit7eacute; de Paris 6, 1999.
• 2: Philippe Aubry , Dongming Wang, Reasoning about Surfaces Using Differential Zero and Ideal Decomposition, Revised Papers from the Third International Workshop on Automated Deduction in Geometry, p.154-174, September 25-27, 2000
• 3: F. Boulier and E. Hubert. textscdiffalg: description and examples of use. U. of Waterloo, 1998, \www.inria.fr/cafe/Evelyne.Hubert/diffalg.
• 4: 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]
• 5: F. Boulier, D. Lazard, F. Ollivier, and M. Petitot. Computing representations for radicals of finitely generated differential ideals. Technical Report IT-306, LIFL, 1997.
• 6: François Boulier , François Lemaire, Computing canonical representatives of regular differential ideals, Proceedings of the 2000 international symposium on Symbolic and algebraic computation, p.38-47, July 2000, St. Andrews, Scotland [doi>10.1145/345542.345571]
• 7: François Boulier , François Lemaire , Marc Moreno Maza, PARDI!, Proceedings of the 2001 international symposium on Symbolic and algebraic computation, p.38-47, July 2001, London, Ontario, Canada [doi>10.1145/384101.384108]
• 8: 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]
• 9: G. Carra Ferro. Grübner bases and differential algebra. In AAECC, volume 356 of Lecture Notes in Computer Science. Springer-Verlag, 1987.
• 10: S-C. Chou and X-S. Gao. Automated reasonning in differential geometry and mechanics using the characteristic set method. Part II. Mechanical theorem proving. Journal of Automated Reasonning, 10:173--189, 1993.
• 11: Peter A. Clarkson , Elizabeth L. Mansfield, Symmetry reductions and exact solutions of a class of nonlinear heat equations, Physica D, v.70 n.3, p.250-288, Jan. 15, 1994 [doi>10.1016/0167-2789(94)90017-5]
• 12: George E. Collins, Subresultants and Reduced Polynomial Remainder Sequences, Journal of the ACM (JACM), v.14 n.1, p.128-142, Jan. 1967 [doi>10.1145/321371.321381]
• 13: S. Dellière. Triangularisation de systèmes constructibles. Application à l'évaluation dynamique. PhD thesis, Univ. de Limoges, 1999.
• 14: L. Ducos. Optimizations of the subresultant algorithm. Journal of Pure and Applied Algebra, 145(2):149--163, 2000.
• 15: M. Fliess and S.T. Glad. An algebraic approach to linear and nonlinear control. In Essays on control: Perspectives in the theory and its applications, volume 14. Birkhäuser, Boston, 1993.
• 16: T. Gómez-Dîaz. Applications de l'évaluation dynamique. PhD thesis, Univ. de Limoges, 1994.
• 17: 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]
• 18: E. Hubert. Notes on triangular sets and triangulation-decomposition algorithms I: Polynomial systems. In Winkler and Langer.
• 19: E. Hubert. Notes on triangular sets and triangulation-decomposition algorithms II: Differential systems. In Winkler and Langer.
• 20: E. Hubert , N. Le Roux, Computing power series solutions of a nonlinear PDE system, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.148-155, August 03-06, 2003, Philadelphia, PA, USA [doi>10.1145/860854.860891]
• 21: Michael Kalkbrener, A generalized Euclidean algorithm for computing triangular representations of algebraic varieties, Journal of Symbolic Computation, v.15 n.2, p.143-167, Feb. 1993 [doi>10.1006/jsco.1993.1011]
• 22: A. A. Kapaev and E. Hubert. A note on the Lax pairs for Painlevé equations. Journal of Physics. A. Mathematical and General, 32(46), 1999.
• 23: E. R. Kolchin. Differential Algebra and Algebraic Groups, volume 54 of Pure and Applied Mathematics. Academic Press, 1973.
• 24: Francois Lemaire. Les classements les plus généraux assurant l'analycité des solutions des systèmes orthonomes pour des conditions initiales analytiques. In CASC 2002. Technische Universität München, Germany, 2002.
• 25: Henri Lombardi , Marie-Françoise Roy , Mohad Safey El Din, New structure theorem for subresultants, Journal of Symbolic Computation, v.29 n.4-5, p.663-690, April/May 2000 [doi>10.1006/jsco.1999.0322]
• 26: E. L. Mansfield. Differential Gröbner Bases. PhD thesis, University of Sydney, 1991.
• 27: E. L. Mansfield, G. J. Reid, and P. A. Clarkson. Nonclassical reductions of a 3+1-cubic nonlinear Schrödinger system. Computer Physics Communications, 115:460--488, 1998.
• 28: G. Margaria, E. Riccomagno, M. J. Chappell, and H. P. Wynn. Differential algebra methods for the study of the structural identifiability of rational function state-space models in the biosciences. Mathematical Biosciences, 174(1):1--26, 2001.
• 29: Bhubaneswar Mishra, Algorithmic algebra, Springer-Verlag New York, Inc., New York, NY, 1993
• 30: M. Moreno-Maza. Calculs de pgcd au-dessus des tours d'extensions simples et résolution des systèmes d'équations algébriques. PhD thesis, Université Paris 6, 1997.
• 31: 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
• 32: F. Ollivier and A. Sedoglavic. Algorithmes efficacxes pour tester l'identifiabilité locale. In Conférence Internationale Francophone d'Automatique. IEEE, 2002.
• 33: C. Riquier. Les systèmes d'équations aux dérivées partielles. Gauthier-Villars, Paris, 1910.
• 34: J. F. Ritt. Differential Algebra, volume XXXIII of Colloquium publications. American Mathematical Society, 1950. \tt http://www.ams.org/online\_bks.
• 35: Colin James Rust , William Fulton, Rankings of derivatives for elimination algorithms and formal solvability of analytic partial differential equations, 1998
• 36: 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]
• 37: A. Seidenberg. An elimination theory for differential algebra. University of California Publications in Mathematics, 3(2):31--66, 1956.
• 38: D. Wang. An elimination method for differential polynomial systems. I. Systems Science and Mathematical Sciences, 9(3):216--228, 1996.
• 39: Dongming Wang, Decomposing polynomial systems into simple systems, Journal of Symbolic Computation, v.25 n.3, p.295-314, March 1998 [doi>10.1006/jsco.1997.0177]
• 40: Dongming Wang, Computing triangular systems and regular systems, Journal of Symbolic Computation, v.30 n.2, p.221-236, Aug. 2000 [doi>10.1006/jsco.1999.0355]
• 41: F. Winkler and U. Langer, editors. Symbolic and Numerical Scientific Computing, volume 2630 of LNCS. Springer Verlag, 2003.
• 42: 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:
differential elimination, differential ideal theory, subresultant polynomial remainder sequence, systems of differential equations, triangular sets