skip to main content
10.1145/1005285.1005314acmconferencesArticle/Chapter ViewAbstractPublication PagesissacConference Proceedingsconference-collections
Article

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

Published: 04 July 2004 Publication History

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]
P. Aubry and D. Wang. Reasonning about surfaces using differential zero and ideal decomposition. In ADG 2000, number 2061 in LNAI, 2001.]]
[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, and M. Petitot. Representation for the radical of a finitely generated differential ideal. In ISSAC'95. ACM, 1995.]]
[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]
F. Boulier and F. Lemaire. Computing canonical representatives of regular differential ideals. In ISSAC 2000. ACM, 2000.]]
[7]
F. Boulier, F. Lemaire, and M. Moreno-Maza. Pardi! In ISSAC 2001. ACM, 2001.]]
[8]
D. Bouziane, A. Kandri Rody, and H. Maârouf. Unmixed-dimensional decomposition of a finitely generated perfect differential ideal. Journal of Symbolic Computation, 31(6):631--649, 2001.]]
[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]
P. A. Clarkson and E. L. Mansfield. Symmetry reductions and exact solutions of a class of non-linear heat equations. Physica, D70:250--288, 1994.]]
[12]
G. E. Collins. Subresultants and reduced polynomial remainder sequences. J. Assoc. Comput. Mach., 14:128--142, 1967.]]
[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]
E. Hubert. Factorisation free decomposition algorithms in differential algebra. Journal of Symbolic Computation, 29(4-5):641--662, 2000.]]
[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 and N. Le Roux. Computing power series solutions of a nonlinear pde system. In ISSAC 2003. ACM, 2003.]]
[21]
M. Kalkbrener. A generalized Euclidean algorithm for computing triangular representations of algebraic varieties. Journal of Symbolic Computation, 15(2):143--167, 1993.]]
[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]
H. Lombardi, M-F. Roy, and M. S. El Din. New structure theorem for subresultants. Journal of Symbolic Computation, 29(4-5):663--690, 2000.]]
[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]
B. Mishra. Algorithmic Algebra, volume XIV of Texts and Monographs in Computer Science. Springer-Verlag New York, 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]
F. Ollivier. Standard bases of differential ideals. In AAECC'90, pages 304--321. Springer, 1991.]]
[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]
C. Rust. Rankings of derivatives for elimination algorithms and formal solvability of analytic partial differential equations. PhD thesis, University of Chicago, 1998.]]
[36]
C. J. Rust, G. J. Reid, and A. D. Wittkopf. Existence and uniqueness theorems for formal power series solutions of analytic differential systems. In ISSAC'99. ACM, 1999.]]
[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]
D. Wang. Decomposing polynomial systems into simple systems. Journal of Symbolic Computation, 25(3):295--314, 1998.]]
[40]
D. Wang. Computing triangular systems and regular systems. Journal of Symbolic Computation, 30(2):221--236, 2000.]]
[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.]]

Cited By

View all
  • (2020)On the chordality of ordinary differential triangular decomposition in top-down styleProceedings of the 45th International Symposium on Symbolic and Algebraic Computation10.1145/3373207.3403999(364-371)Online publication date: 20-Jul-2020
  • (2020)Algorithm for computing differential char sets efficientlyJournal of Discrete Mathematical Sciences and Cryptography10.1080/09720529.2020.180911423:6(1203-1216)Online publication date: 27-Oct-2020
  • (2008)Probabilistic algorithms for computing resolvent representations of regular differential idealsApplicable Algebra in Engineering, Communication and Computing10.1007/s00200-008-0079-819:5(365-392)Online publication date: 1-Oct-2008

Index Terms

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

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      ISSAC '04: Proceedings of the 2004 international symposium on Symbolic and algebraic computation
      July 2004
      334 pages
      ISBN:158113827X
      DOI:10.1145/1005285
      • General Chair:
      • Josef Schicho
      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Sponsors

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 04 July 2004

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. differential elimination
      2. differential ideal theory
      3. subresultant polynomial remainder sequence
      4. systems of differential equations
      5. triangular sets

      Qualifiers

      • Article

      Conference

      ISSAC04
      Sponsor:

      Acceptance Rates

      Overall Acceptance Rate 395 of 838 submissions, 47%

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)0
      • Downloads (Last 6 weeks)0
      Reflects downloads up to 14 Feb 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2020)On the chordality of ordinary differential triangular decomposition in top-down styleProceedings of the 45th International Symposium on Symbolic and Algebraic Computation10.1145/3373207.3403999(364-371)Online publication date: 20-Jul-2020
      • (2020)Algorithm for computing differential char sets efficientlyJournal of Discrete Mathematical Sciences and Cryptography10.1080/09720529.2020.180911423:6(1203-1216)Online publication date: 27-Oct-2020
      • (2008)Probabilistic algorithms for computing resolvent representations of regular differential idealsApplicable Algebra in Engineering, Communication and Computing10.1007/s00200-008-0079-819:5(365-392)Online publication date: 1-Oct-2008

      View Options

      Login options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media