Welcome! | Research Topics | People | Publications | Seminars | Software | On-Line Applications | Jobs & Internships |
Frédéric Chyzak's Mgfun Project |
Ore_algebra, Groebner, Mgfun, and Other Packages | Publications, Notes, and Slides |
Introduction | Example Sessions | Download Packages | Known Bugs | FAQ | The Package Gfun | Related Publications | Related Links | F. Chyzak's Home Page |
The Mgfun Project is a collection of packages for the computer algebra system Maple, and is intended for the symbolic manipulation of a large class of special functions and combinatorial sequences (in one or several variables and indices) that appear in many branches of mathematics, mathematical physics, and engineering sciences. Members of the class satisfy a crucial finiteness property which makes the class amenable to computer algebra methods and enjoy numerous algorithmic closure properties, including algorithmic closures under integration and summation.
Much more than the search for closed forms, the aim is to be able to continue to compute with the implicit representation of holonomic objects even when no explicit form is available. Applications include the simplification of expressions in special functions and sequences, the evaluation of parametrized definite integrals and sums, series and asymptotic expansions, the automatic proof of identities, and will open to the fast numerical evaluation of special functions in the future. To achieve these goals, several algorithmic tools are used by Mgfun, and have been implemented as separate dedicated packages. The implementation has made it possible to give the first automatic proof of identities so far unreachable by computer algebra. The Mgfun family consists of:
Implicit Representations of Special Functions and Sequences. The essence of the Mgfun packages is to base on implicit representations of special functions and combinatorial sequences in terms of systems of linear functional equations, rather than explicit closed forms. In order to accomodate linear operators of a general type, like linear differential and linear finite difference operators, a class of algebras of multivariate skew polynomials is introduced, namely Ore algebras. Although they are non-commutative, these algebras share many algorithmic properties with the usual commutative polynomial algebras, like the existence of a degree, a gcd theory, a euclidean algorithm. Moreover, they are used more and more in recent computer algebra algorithms as a tool to unify differential calculations with functions and calculations of recurrences with sequences. Their algorithmic aspects have been implemented in the package Ore_algebra.
Gröbner Bases in Algebras of Linear Operators. Many special functions and combinatorial sequences can be defined as the common solutions of systems of linear functional equations. In this spirit, Mgfun views special functions and combinatorial sequences as the zeroes of special left ideals in Ore algebras. Algorithms to manipulate special functions and sequences then appeal to polynomial elimination in those algebras of linear operators, for which methods of non-commutative Gröbner bases have been developed. Indeed, the simple commutation rules that describe the non-commutativity of Ore algebras make it possible to develop a theory of Gröbner bases together with an extension of Buchberger's algorithm whose termination is always guaranteed. Other natural extensions of Gröbner-based calculations (FGLM algorithm, Gröbner bases for modules, computation of syzygies, Gröbner walk, ...) exist in the skew setting and can be put to good use in applications. The package Groebner implements many of them. It provides Gröbner bases for many algebras and many term orderings.
Holonomy and Holonomic Functions. The approach followed by packages in the Mgfun family originates from work by D. Zeilberger at the beginning of the 1990's. Zeilberger's interesting observation is the relevance of the theory of holonomic D-modules to the problem of summation and integration of special functions and combinatorial sequences. This theory had originally been developed by J. Bernstein in the 1970's in order to answer a question of analytical nature, namely the existence of a meromorphic extension of a certain function known to be analytic in a half of the complex plane. In both types of applications, the role of holonomy is to ensure the existence of a linear operator with a special elimination property. Bernstein's holonomic modules specifically refer to modules over algebras of linear differential operators. Their definition relates to a dimension theory for ideals. Zeilberger suggested a definition in the case of linear recurrence operators. The case of algebras of linear q-difference operators was then developed in the 1990's.
Holonomic Summation and Integration. After Zeilberger's original work, algorithmic closures under summation and integration following the holonomic approach have been intensively studied in the 1990's, leading to a great deal of algorithms. The problem still stimulates vivid ongoing research. The package Holonomy implements several of these integration and summation algorithms, ranging from a brute-force elimination algorithm by Gröbner basis calculation to subtle algorithms based on a restricted kind of elimination. Specifically, the package provides the user with a toolbox for calculations with holonomic functions in their ideal-theoretic representation, and can be used to study sutble properties of holonomic functions. This is complemented at a higher level by the package Mgfun, a user-oriented interface to the previous packages, much in the spirit of the package Gfun dedicated to the univariate case.
Each of the packages has its introductory Maple session.
Ore_algebra (html) | Groebner (html) | Mgfun (html) |
Ore_algebra (mws) | Groebner (mws) | Mgfun (mws) |
Ore_algebra (ps) | Groebner (ps) | Mgfun (ps) |
Besides, a few Maple sessions accompany Frédéric Chyzak's publications that are related to Mgfun. An older demo based on an earlier version of the software is also available.
All the packages described above, as well as other packages developed by the Algo team, conveniently come together in the algolib library for Maple V.5. A Maple V.4 version is also available for people who have no access to Maple V.5. However, this version does not include the whole algolib library and does not make on-line help pages available. In case of any trouble when downloading or installing the software, please contact the author.
The following are publications that describe the theoretical aspects implemented in the packages.
Holonomy is a recurrent topic discussed at the Algorithm Seminar. Here are a few summaries of sessions dedicated to it:
Here are also seminar summaries of sessions about related topics, either applications or algorithms to be used internally in Mgfun: