Titre Une implémentation générique et efficace des bases involutives.

English version

Lieu

INRIA, Projet CAFÉ
BP 93, 06902 France

Information

Manuel Bronstein and Alban Quadrat

Description

La complétion involutive est une alternative aux bases de Groebner qui représente une première étape de la résolution de systèmes d'équations soit polynomiales [3], ou bien aux dérivées partielles linéaires [2,7]. Il existe plusieurs implémentations de la complétion de Janet (une sorte particulière de complétion involutive) dans divers systèmes de calcul formel, ainsi qu'une implémentation très efficace en C++ pour les équations polynomiales [4,5]. La complétion de Pommaret (une autre sorte) est elle implémentée dans le paquetage d'involution très général de MuPAD [6], mais pas aussi efficacement que dans [4,5].
Le but de ce stage est d'utiliser la généricité du langage de programmation Aldor pour produire une implémentation de la complétion involutive qui soit à la fois générale et hautement efficace. La généralité sera obtenue, comme dans [6], en paramétrisant le programme par la sorte de division involutive à utiliser. Quant à l'efficacité, elle sera obtenue en implémentant les divisions involutives de Janet et de Pommaret avec les structures de données et algorithmes de [4,5]. Si le temps le permet, une généralisation possible de la complétion vers les algèbres de Ore de [1] sera étudiée.

[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.

Outils

Station de travail Unix, langage de programmation Aldor, avec la bibliothèque Algebra.

Durée

3 - 4 mois, niveau stage d'ingénieur ou DEA.