×

zbMATH — the first resource for mathematics

Minimal involutive bases. (English) Zbl 1017.13501
Summary: We present an algorithm for construction of minimal involutive polynomial bases which are Gröbner bases of the special form. The most general involutive algorithms are based on the concept of involutive monomial division which leads to partition of variables into multiplicative and non-multiplicative. This partition gives thereby the self-consistent computational procedure for constructing an involutive basis by performing non-multiplicative prolongations and multiplicative reductions. Every specific involutive division generates a particular form of involutive computational procedure. In addition to three involutive divisions used by Thomas, Janet and Pommaret for analysis of partial differential equations we define two new ones. These two divisions, as well as Thomas division, do not depend on the order of variables. We prove noetherity, continuity and constructivity of the new divisions that provides correctness and termination of involutive algorithms for any finite set of input polynomials and any admissible monomial ordering. We show that, given an admissible monomial ordering, a monic minimal involutive basis is uniquely defined and thereby can be considered as canonical much like the reduced Gröbner basis.

MSC:
13P99 Computational aspects and applications of commutative rings
68W30 Symbolic computation and algebraic computation
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] B. Buchberger, An Algorithm for Finding a Basis for the Residue Class Ring of a Zero-dimensional Polynomial Ideal (in German), PhD Thesis, University of Innsbruck, Austria, 1965 · Zbl 1245.13020
[2] D. Cox, J. Little, D. O’Shea, Ideals, Varieties and Algorithms, An Introduction to Computational Algebraic Geometry and Commutative Algebra, 2nd ed., Springer, New-York, 1995
[3] T. Becker, V. Weispfenning, H. Kredel, Gröbner Bases, A Computational Approach to Commutative Algebra, Graduate Texts in Mathematics 141, Springer, New York, 1993 · Zbl 0772.13010
[4] B. Mishra, Algorithmic Algebra, Springer, New York, 1993 · Zbl 0804.13009
[5] Mora, T.: An introduction to commutative and non-commutative Gröbner bases. Theor. comp. Sci. 134, 131-173 (1994) · Zbl 0824.68056
[6] Kandri-Rody, A.; Weispfenning, V.: Non-cummutative Gröbner bases in algebras of solvable type. J. symb. Comp. 9, 1-26 (1990) · Zbl 0715.16010
[7] A.A. Mikhalev, A.A. Zolotykh, Combinatiorial Aspects of Lie Superalgebras, CRC Press, Boca Raton, New York, 1995 · Zbl 0871.17002
[8] Carra’ferro, G.: Gröbner bases of differential algebra. Lec. not. Comp. sci. 356, 129-140 (1987)
[9] Ollivier, F.: Standard bases of differential ideals. Lec. not. Comp. sci. 508, 304-321 (1990) · Zbl 0737.13009
[10] B. Buchberger, A Criterion for Deteching Unnecessary Reductions in the Construction of Gröbner Bases, in: E.W. Ng, (Ed.), Proceedings of EUROSAM 79, Springer, Berlin, 1979, pp. 3–21 · Zbl 0417.68029
[11] B. Buchberger, Gröbner Bases: an Algorithmic Method in Polynomial Ideal Theory, in: N.K. Bose (ed.), In Recent Trends in Multidimensional System Theory, Reidel, Dordrecht, 1985, pp. 184–232 · Zbl 0587.13009
[12] Gebauer, R.; Möller, H. M.: On an installation of buchberger’s algorithm. J. symb. Comp. 6, 275-286 (1988) · Zbl 0675.13013
[13] A. Giovini, T. Mora, G. Niesi, L. Robbiano, C. Traverso, One sugar cube, please’ or selection strategies in the Buchberger algorithm, in: S.M. Watt (Ed.), Proceedings of the ISSAC’91, ACM Press, 1991, pp. 49–54 · Zbl 0933.68161
[14] Faugère, J. C.; Gianni, P.; Lazard, D.; Mora, T.: Efficient computation of zero-dimensional Gröbner bases by change of ordering. J. symb. Comp. 16, 329-344 (1993) · Zbl 0805.13007
[15] A.Yu. Zharkov, Yu.A. Blinkov, Involutive Approach to Investigating Polynomial Systems, In: Proceedings of SC 93, International IMACS Symposium on Symbolic Computation: New Trends and Developments (Lille, June 14–17, 1993), Math. Comp. Simul. 42 (1996), 323-332
[16] J.F. Pommaret, Systems of Partial Differential Equations and Lie Pseudogroups, Gordon & Breach, New York, 1978 · Zbl 0418.35028
[17] Janet, M.: Sur LES systèmes d’equations aux dérivées partielles. J. math. Pure et appl. 3, 65-151 (1920)
[18] A.Yu. Zharkov, Solving Zero-Dimensional Involutive Systems, L. Gonzales-Vega, T. Recio (eds.), in: Algorithms in Algebric Geometry and Applications, Progress in Mathematics, Vol. 143, Birkhäuser, Basel, 1996, pp. 389–399
[19] A.Yu. Zharkov, Yu.A. Blinkov, Involutive Bases of Zero-Dimensional Ideals. Preprint No. E5-94-318, Joint Institute for Nuclear Research, Dubna, 1993 · Zbl 0828.13020
[20] Apel, J.: A Gröbner approach to involutive bases. J. symb. Comp. 19, 441-457 (1995) · Zbl 0857.13027
[21] Garcı\acutea-Sánchez, P. A.: Gröbner and involutive bases for zero-dimensional ideals. SIGSAM bulletin 29, No. 2, 12-15 (1995) · Zbl 1095.13549
[22] V.P. Gerdt, Yu.A. Blinkov, Involutive Bases of Polynomial Ideals, Preprint-Nr. 1/1996, Naturwissenschaftlich-Theoretisches Zentrum, University of Leipzig, 1996, This issue
[23] J. Thomas, Differential Systems, American Mathematical Society, New York, 1937 · JFM 63.0438.03
[24] Schwarz, F.: An algorithm for determining the size of symmetry groups. Computing 49, 95-115 (1992) · Zbl 0759.68042
[25] V.P. Gerdt, Gröbner Bases and Involutive Methods for Algebraic and Differential Equations, in: J. Fleischer, J. Grabmeier, F.W. Hehl, W. Küchlin (Eds.), Computer Algebra in Science and Engineering, World Scientific, Singapore, 1995, pp. 117–137
[26] V.P. Gerdt, Involutive Division Methods Applied to Algebraic and Differential Equations, In preparation · Zbl 0904.13014
[27] C. Riquier, Les Systèmes d’Equations aux Dérivées Partielles, Gauthier-Villars, Paris, 1910
[28] Reid, G. J.: Algorithms for reducing a system of pdes to standard form, determining the dimension of its solution space and calculating its Taylor series solution. Euro. J. Appl. maths. 2, 293-318 (1992) · Zbl 0768.35001
[29] W.M. Seiler, Analysis and Application of the Formal Theory of Partial Differential Equations, PhD Thesis, Lancaster University, 1994
[30] V.P. Gerdt, V.V. Kornyak, Construction of Finitely Presented Lie Algebras and Superalgebras, J. Symb. Comp., 21, pp. 337–349 · Zbl 0876.17002
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.