Computing representations for radicals of finitely generated differential ideals. (English) Zbl 1185.12003
This article presents an improvement of the Rosenfeld-Gröbner algorithm (details below), which computes a representation for the radical of the differential ideal generated by any system of differential polynomial equations, ordinary or partial. This allows testing membership in the radical ideal and also computing Taylor expansions of solutions of the original system. The core of the algorithm is to express radical differential ideals as intersections of regular differential ideals. The authors have implemented their algorithm as a MAPLE package.
The authors improve some results of a previous work [Proceedings of the 1995 international symposium on symbolic and algebraic computation, ISSAC ’95, Montreal, Canada, July 10–12, 1995. New York, NY: ACM Press, 158–166 (1995; Zbl 0911.13011)], making the algorithm much more efficient than the previous version. According to them, the Rosenfeld-Gröbner algorithm compares favourably to the similar algorithm by A. Seidenberg [Univ. California Publ. Math., n. Ser. 3, 31–66 (1957; Zbl 0083.03302)] and in fact Section 0.3 is devoted to comparing the presented method with other ones in the literature.
Section 2 contains an improved proof of Lazard’s Lemma, which “establishes that each regular ideal is radical and that all its prime components have a same parametric set” including details on performing computations in dimension zero. Section 4 proves the authors’ version of Rosenfeld’s Lemma which “gives a sufficient condition so that a system of polynomial differential equations admits a solution if and only if this same system, considered as a purely algebraic system admits a solution” and auxiliary technical results. Section 5 describes how to represent radical differential ideals as intersections of regular differential ideals. In Section 6 it is shown how to compute canonical representatives for regular differential ideals and the main algorithm is stated as a theorem and proven effectively. Section 7 explains how to expand algebraic solutions as formal power series. Finally examples are given in some detail.
The authors improve some results of a previous work [Proceedings of the 1995 international symposium on symbolic and algebraic computation, ISSAC ’95, Montreal, Canada, July 10–12, 1995. New York, NY: ACM Press, 158–166 (1995; Zbl 0911.13011)], making the algorithm much more efficient than the previous version. According to them, the Rosenfeld-Gröbner algorithm compares favourably to the similar algorithm by A. Seidenberg [Univ. California Publ. Math., n. Ser. 3, 31–66 (1957; Zbl 0083.03302)] and in fact Section 0.3 is devoted to comparing the presented method with other ones in the literature.
Section 2 contains an improved proof of Lazard’s Lemma, which “establishes that each regular ideal is radical and that all its prime components have a same parametric set” including details on performing computations in dimension zero. Section 4 proves the authors’ version of Rosenfeld’s Lemma which “gives a sufficient condition so that a system of polynomial differential equations admits a solution if and only if this same system, considered as a purely algebraic system admits a solution” and auxiliary technical results. Section 5 describes how to represent radical differential ideals as intersections of regular differential ideals. In Section 6 it is shown how to compute canonical representatives for regular differential ideals and the main algorithm is stated as a theorem and proven effectively. Section 7 explains how to expand algebraic solutions as formal power series. Finally examples are given in some detail.
Reviewer: David Sevilla (Linz)
MSC:
| 12H05 | Differential algebra |
| 13N05 | Modules of differentials |
| 68W30 | Symbolic computation and algebraic computation |
| 13P99 | Computational aspects and applications of commutative rings |
Software:
MapleReferences:
| [1] | Becker T., Weispfenning V. (1991) Gröbner Bases: A Computational Approach to Commutative Algebra. Graduate Texts in Mathematics, vol. 141. Springer, New York · Zbl 0925.13013 |
| [2] | Boulier, F.: Étude et Implantation de Quelques Algorithmes en Algèbre Différentielle. PhD thesis, Université Lille I, 59655, Villeneuve d’Ascq, France (1994). http://tel.archives-ouvertes.fr/tel-00137866 |
| [3] | Boulier, F.: Some improvements of a lemma of Rosenfeld (never published) (1997) |
| [4] | Boulier, F., Lazard, D., Ollivier, F., Petitot, M.: Representation for the radical of a finitely generated differential ideal. In: ISSAC’95: Proceedings of the 1995 International Symposium on Symbolic and Algebraic Computation, pp. 158–166, ACM Press, New York (1995). ISBN 0-89791-699-9. http://hal.archives-ouvertes.fr/hal-00138020 · Zbl 0911.13011 |
| [5] | Bouziane D., Kandri Rody A., Maârouf H. (2001) Unmixed-dimensional decomposition of a finitely generated perfect differential ideal. J. Symb. Comput. 31: 631–649 · Zbl 1038.12005 · doi:10.1006/jsco.1999.1562 |
| [6] | Buchberger, B.: A Criterion for Detecting Unnecessary Reductions in the Construction of Gröbner Bases. Lecture Notes in Computer Science, vol. 72, pp. 3–21. Springer, New York (1979) · Zbl 0417.68029 |
| [7] | Carra-Ferro, G.: Gröbner bases and differential ideals. In: Proceedings of AAECC 5, pp. 129–140, Springer, Menorca (1987) |
| [8] | Cox, D., Little, J., O’Shea, D.: Ideals, Varieties and Algorithms. An Introduction to Computational Algebraic Geometry and Commutative Algebra. Undergraduate Texts in Mathematics. Springer, New York (1992) · Zbl 0756.13017 |
| [9] | Eisenbud, D.: Commutative Algebra with a View Toward Algebraic Geometry. Graduate Texts in Mathematics, vol. 150. Springer, New York (1995) · Zbl 0819.13001 |
| [10] | Gallo G., Mishra B., Ollivier F. (1991) Some constructions in rings of differential polynomials. Lect. Notes Comput. Sci. 539: 171–182 · Zbl 0787.13015 |
| [11] | Gebauer R., Möller H.M. (1988) On an installation of Buchberger’s algorithm. J. Symb. Comput. 6(2-3): 275–286 · Zbl 0675.13013 · doi:10.1016/S0747-7171(88)80048-8 |
| [12] | Hubert, é.: Étude Algébrique et algorithmique des Singularités des Équations Différentielles Implicites. PhD thesis, Institut National Polytechnique de Grenoble, France (1997) |
| [13] | Janet, M.: Systèmes d’Équations aux Dérivées Partielles. Journal de Mathématiques, 8 e Série, vol. 3. Gauthier-Villars, Paris (1920) · JFM 47.0440.04 |
| [14] | Janet, M.: Leçons sur les Systèmes d’Équations aux Dérivées Partielles. Cahiers Scientifiques, vol. IV. Gauthier-Villars, Paris (1929) · JFM 55.0276.01 |
| [15] | Kalkbrener M. (1993) A generalized euclidean algorithm for computing triangular representations of algebraic varieties. J. Symb. Comput. 15: 143–167 · Zbl 0783.14039 · doi:10.1006/jsco.1993.1011 |
| [16] | Knuth D.E. (1966) The Art of Computer Programming, 2nd edn. Addison-Wesley, Reading · Zbl 0231.68027 |
| [17] | Kolchin E.R. (1973) Differential Algebra and Algebraic Groups. Academic Press, New York · Zbl 0264.12102 |
| [18] | Konig D. (1950) Theorie der Endlichen und Unendlichen Graphen. Chelsea, New York |
| [19] | Lazard D. (1992) Solving zero-dimensional algebraic systems. J. Symb. Comput. 13: 117–131 · Zbl 0753.13012 · doi:10.1016/S0747-7171(08)80086-7 |
| [20] | Levi H. (1945) The low power theorem for partial differential equations. Ann. Math. Soc. 46: 113–119 · Zbl 0061.20503 · doi:10.2307/1969151 |
| [21] | Maârouf, H.: Étude de Quelques Problèmes Effectifs en Algèbre Différentielle. PhD thesis, Université Cadi Ayyad, Morocco (1996) |
| [22] | Mansfield, E.L.: Differential Gröbner Bases. PhD thesis, University of Sydney, Australia (1991) |
| [23] | Moreno Maza, M.: Calculs de Pgcd au-dessus des Tours d’Extensions Simples et Résolution des Systèmes d’Équations Algébriques. PhD thesis, Université Paris VI, France (1997) |
| [24] | Morrison, S.: Yet another proof of Lazard’s lemma. Private communication (1995) |
| [25] | Morrison S. (1999) The differential ideal [P] : M J. Symb. Comput. 28: 631–656 · Zbl 1053.12503 · doi:10.1006/jsco.1999.0318 |
| [26] | Ollivier, F.: Le Problème de l’Identifiabilité Structurelle Globale: Approche Théorique, Méthodes Effectives et Bornes de Complexité. PhD thesis, École Polytechnique, Palaiseau, France (1990) |
| [27] | Ollivier, F.: A proof of Lazard’s lemma. Private communication (1998) |
| [28] | Olver, P.J.: Applications of Lie Groups to Differential Equations. Graduate Texts in Mathematics, vol. 107, 2nd edn. Springer, New York (1993) · Zbl 0785.58003 |
| [29] | Olver P.J. (1995) Equivalence, Invariants and Symmetry. Cambridge University Press, New York · Zbl 0837.58001 |
| [30] | Péladan-Germa, A.: Tests Effectifs de Nullité Dans des Extensions d’Anneaux Différentiels. PhD thesis, École Polytechnique, Palaiseau, France (1997) |
| [31] | Reid G.J. (1991) Algorithms for reducing a system of PDEs to standard form determining the dimension of its solution space and calculating its Taylor series solution. Eur. J. Appl. Math. 2: 293–318 · Zbl 0768.35001 · doi:10.1017/S0956792500000577 |
| [32] | Reid G.J., Wittkopf A.D., Boulton A. (1996) Reduction of systems of nonlinear partial differential equations to simplified involutive forms. Eur. J. Appl. Math. 7(6): 635–666 · Zbl 0892.35041 · doi:10.1017/S0956792500002618 |
| [33] | Reid G.J., Lin P., Wittkopf A.D. (2001) Differential elimination-completion algorithms for DAE and PDAE. Stud. Appl. Math. 106(1): 1–45 · Zbl 1152.65458 · doi:10.1111/1467-9590.00159 |
| [34] | Riquier C. (1910) Les Systèmes d’Équations aux Dérivées Partielles. Gauthier-Villars, Paris |
| [35] | Ritt, J.F.: Differential Equations from the Algebraic Standpoint. American Mathematical Society Colloquium Publications, vol. 14. AMS, New York (1932) · Zbl 0005.39404 |
| [36] | Ritt, J.F.: Differential Algebra. Dover, New York (1950). http://www.ams.org/online_bks/coll33 · Zbl 0037.18402 |
| [37] | Rosenfeld A. (1959) Specializations in differential algebra. Trans. Am. Math. Soc. 90: 394–407 · Zbl 0192.14001 · doi:10.1090/S0002-9947-1959-0107642-2 |
| [38] | Schicho, J., Li, Z.: A construction of radical ideals in polynomial algebra. Technical report, RISC, Johannes Kepler University, Linz, Austria, August (1995) |
| [39] | Seidenberg A. (1952) Some basic theorems in differential algebra(characteristic p arbitrary). Trans. Am. Math. Soc. 73: 174–190 · Zbl 0047.03502 |
| [40] | Seidenberg A. (1956) An elimination theory for differential algebra. Univ. Calif. Publ. Math. (New Series) 3: 31–65 · Zbl 0072.26502 |
| [41] | Seidenberg A. (1958) Abstract differential algebra and the analytic case. Proc. Am. Math. Soc. 9: 159–164 · Zbl 0186.07502 · doi:10.1090/S0002-9939-1958-0093655-0 |
| [42] | Seidenberg A. (1969) Abstract differential algebra and the analytic case II. Proc. Am. Math. Soc. 23: 689–691 · Zbl 0186.07503 · doi:10.1090/S0002-9939-1969-0248122-5 |
| [43] | Waerden B.L. (1966) Algebra, 7th edn. Springer, Berlin · Zbl 0137.25403 |
| [44] | Wang, D.: An elimination method for differential polynomial systems I. Technical report, LIFIA–IMAG, Grenoble, France (1994) |
| [45] | Tsün W.W. (1989) On the foundation of algebraic differential geometry. Mechanization Math. 3: 2–27 (research preprints) |
| [46] | Zariski, O., Samuel, P.: Commutative Algebra. Van Nostrand, New York (1958). Also volumes 28 and 29 of the Graduate Texts in Mathematics. Springer, New York |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
