Computing canonical representatives of regular differential ideals

ABSTRACT

In this paper, we give three theoretical and practical contributions for solving polynomial ODE or PDE systems. The first one is practical: an algorithm which improves the purely algebraic part of Rosenfeld—Gröbner (the polynomial ODE or PDE systems simplifier which is the core of the Maple 5.5 diffalg package). It is a variant of lextriangular but does not need any Gröbner basis computation. The second one is theoretical: a characterization of the output of Rosenfeld—Gröbner and a clarification of the existing relationship between algebraic and differential characteristic sets. The third one is theoretical as well as practical: an algorithm to compute canonical representatives of differential polynomials modulo regular differential ideals without any use of Gröbner bases. This algorithm simplifies the theory (somehow a “pedagogic” contribution) but permits us also to perform easily linear algebra over the base field in the factor differential ring defined by a regular differential ideal.

REFERENCES

• 1: P. Aubry. Ensembles triangulaires de polyn6mes et resolution de syst~mes alg~briques. Implantation en Axiom. PhD thesis, Universit~ Paris VI, 1999.
• 2: Philippe Aubry , Daniel Lazard , Marc Moreno Maza, On the theories of triangular sets, Journal of Symbolic Computation, v.28 n.1-2, p.105-124, July/Aug. 1999 [doi>10.1006/jsco.1999.0269]
• 3: Thomas Becker , Volker Weispfenning , Heinz Kredel, Gro¨bner bases: a computational approach to commutative algebra, Springer-Verlag, London, 1993
• 4: F. Boulier. t~tude et implantation de quelques algorithmes en alg~bre diff~rentielle. PhD thesis, Universit~ Lille I, 59655, Villeneuve d'Ascq, 1994.
• 5: F. Boulier. Efficient computation of regular differential systems by change of rankings using KShler differentials. Technical report (ref. LIFL99-14)
• 6: 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]
• 7: F. Boulier, D. Lazard, F. Ollivier, and M. Petitot. Computing representations for radicals of finitely generated differential ideals. (technical report IT306 of the LIFL, available at http://www, lifl. fr/~boulier).
• 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: B. Buchberger. An Algorithm for Finding a Basis for the Residue Class Ring of a Zero-Dimensional Polynomial Ideal (German). PhD thesis, Math. Inst. Univ. of Innsbruck, Austria, 1965.
• 10: Jean Della Dora , Claire Dicrescenzo , Dominique Duval, About a New Method for Computing in Algebraic Number Fields, Research Contributions from the European Conference on Computer Algebra-Volume 2, p.289-290, April 01-03, 1985
• 11: L. Ducos. Optimizations of the subresultant algorithm. Journal of Pure and Applied Algebra, 1998. (to appear).
• 12: D. Eisenbud. Commutative Algebra with a View Toward Algebraic Geometry, volume 150 of Graduate Texts in Mathematics. Springer Verlag, 1995.
• 13: J. C. Faugère , P. Gianni , D. Lazard , T. Mora, Efficient computation of zero-dimensional Gro¨bner bases by change of ordering, Journal of Symbolic Computation, v.16 n.4, p.329-344, Oct. 1993 [doi>10.1006/jsco.1993.1051]
• 14: 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]
• 15: 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]
• 16: E. R. Kolchin. Differential Algebra and Algebraic Groups. Academic Press, New York, 1973.
• 17: D. KSnig. Theorie der endlichen und unendlichen Graphen. Chelsea publ. Co., New York, 1950.
• 18: D. Lazard, Solving zero-dimensional algebraic systems, Journal of Symbolic Computation, v.13 n.2, p.117-131, Feb. 1992 [doi>10.1016/S0747-7171(08)80086-7]
• 19: Z. Li and D. Wang. Coherent, regular and simple systems in zero decompositions of partial differential systems. Systems Science and Mathematical Sciences, 12:43-60, 1999.
• 20: H. Lombardi, M.-F. Roy, and M. Safey E1 Din. New structure theorem for subresultants. (preprint), 1999.
• 21: H. Maarouf. t~tude de Quelques Probl~mes Effectifs en Alg~bre Diff~rentielle. PhD thesis, Universit~ Cadi Ayyad, Morocco, 1996.
• 22: Marc Moreno Maza , Renaud Rioboo, Polynomial Gcd Computations over Towers of Algebraic Extensions, Proceedings of the 11th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.365-382, July 17-22, 1995
• 23: M. Moreno Maza. Calculs de Pgcd au-dessus des Tours d'Extensions Simples et REsolution des Syst~mes d't~quations Alg~briques. PhD thesis, Universit~ Paris VI, France, 1997.
• 24: Sally Morrison, The differential ideal [P]: M^∞ , Journal of Symbolic Computation, v.28 n.4-5, p.631-656, Oct./Nov. 1999 [doi>10.1006/jsco.1999.0318]
• 25: F. Ollivier. Le probl~me de l'identifiabilit~ structurelle globale : approche th~orique, m~thodes effectives et bornes de complexitY. PhD thesis, l~cole Polytechnique, 91128, Palaiseau, France, 1990.
• 26: J. F. Rift. Differential Algebra. Dover Publications Inc., New York, 1950.
• 27: A. Rosenfeld. Specializations in differential algebra. Trans. Amer. Math. Soc., 90:394-407, 1959.
• 28: J. Schicho and Z. Li. A construction of radical ideals in polynomial algebra. Technical report, RISC, Johannes Kepler University, Linz, Austria, august 1995.
• 29: A. Seidenberg. An elimination theory for differential algebra. Univ. California Publ. Math. (New Series), 3:31-65, 1956.
• 30: 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]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

General Terms:
Algorithms, Theory, Verification

Keywords:
Rosenfeld-Gröbner, canonical representatives, characteristic presentations, characteristic sets, differential algebra, lextriangular, regular differential ideal