Title A generic and efficient implementation of involutive bases. Version française


BP 93, 06902 France


Manuel Bronstein and Alban Quadrat


Completion to involution, an alternative to Groebner bases, is a useful first step when solving either systems of polynomial [3] or linear partial differential [2,7] equations. There are now several implementations of Janet completion (a specific sort of involutive completion) in various computer algebra systems, as well as a highly efficient C++ implementation for polynomial equations [4,5]. Pommaret completion (another sort) is implemented in the quite general involution package of MuPAD [6], but not in as efficient a fashion as in [4,5].
The goal of this internship is to use the genericity features of the Aldor programming language to produce an implementation of completion to involution that is both general and highly efficient. Generality will be obtained, as in [6], by parametrizing the code with the type of involutive division used, and efficiency will be obtained by coding the Janet and Pommaret divisions using the data structures of [4,5]. If time permits, a possible extension from the Weyl algebra to the Ore algebras of [1] will be investigated.

[1] F.Chyzak & B.Salvy (1998): Non-Commutative Elimination in Ore Algebras Proves Multivariate Identities, Journal of Symbolic Computation 26, pp.187-228.

[2] V.Gerdt (1999): Completion of Linear Differential Systems to Involution, in "Proceedings of CASC'99", Springer (Berlin), pp.115-137.

[3] V.Gerdt & Yu.Blinkov (1998): Involutive Bases of Polynomial Ideals, Mathematics and Computers in Simulation 45, pp.519-542.

[4] V.Gerdt, Yu.Blinkov & D.Yanovich (2001): Construction of Janet Bases I.Monomial Bases, in "Proceedings of CASC'2001", Springer (Berlin), pp.233-247.

[5] V.Gerdt, Yu.Blinkov & D.Yanovich (2001): Construction of Janet Bases II.Polynomial Bases, in "Proceedings of CASC'2001", Springer (Berlin), pp.249--263.

[6] M.Hausdorf and W.Seiler (2002): Involutive Bases in MuPAD - Part I: Involutive Divisions, mathPad 11/1, pp.51--56.

[7] F.Schwarz (1998): Janet Bases for Symmetry Groups, in "Groebner Bases and Applications", London Mathematical Society Lecture Notes 251, pp.221-234.


Unix workstation,  the Aldor programming language, with the Algebra library.


3 - 4 months.


November 4, 2002