| Title A generic and efficient implementation of involutive bases. | Version
française |
Location
INRIA, Project
CAFÉ
BP 93, 06902 France
Information
Manuel Bronstein and Alban Quadrat
Description
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.
Tools
Unix workstation, the Aldor programming language, with the Algebra library.
Duration
3 - 4 months.