Algolib: The Algorithms Project's Library and Other Packages of the Algorithms Project

Combinatorics meets computer algebra!

Combinatorial analysis, discrete mathematics and computer algebra are the main interests of the Algorithms Project. Our packages let you specify, generate, and enumerate combinatorial structures; manipulate the associated generating functions, functional equations or recurrences; study their asymptotic behaviour. The interplay between these applications serves the Algorithms Project's main goal of the automatic complexity analysis of algorithms. However, long-term research in this direction has induced the development of other packages for the manipulation of linear differential and difference operators, Groebner basis calculations, and the symbolic summation and integration of special functions and combinatorial sequences.

Special emanations of the above are the algolib library, which collects most of our programs in a single archive, and the encyclopedia of combinatorial structures, which allows access by keywords, combinatorial specifications, generating function, closed-form or by the first integers in the enumeration sequence to many combinatorial structures. A lot of it was automatically generated using combstruct, gfun, and gdev.

Studies in Automatic Combinatorics are extensive example sessions that serve as an introduction to the use of our packages, together with advanced sessions illustrating their use in the study of combinatorics, special functions or asymptotic analysis. Also available as Maple help pages in the algolib library.

Downloading Algolib

The algolib library collects Maple packages developed by the Algo team at INRIA. It currently contains combstruct, encyclopedia, gdev, gfun, Groebner, Holonomy, Mad, Mgfun, MultiSeries, Ore_algebra, and regexpcount. These packages (and more) are described below. An on-line version of the encyclopedia is also available.

Download the Maple10 version... and join the algolib diffusion list (see below)!

Algolib for Maple10 (May 11, 2007).

Previous releases

Algolib for Maple8 (March 11, 2003).

Algolib for Maple7 (August 7, 2002).

Algolib for Maple6 (August 1, 2002).

Algolib for MapleV Release 5 (May 29, 2001).

[The source code of this software is available on request for non-commercial use. Please send your request to frederic.chyzak@inria.fr. We would be more than glad if you could also provide us with information on the work you do and on the use and applications you plan with Algolib.]

Algolib Diffusion List

If you wish to receive electronic announcements of the new releases of algolib, please enter your e-mail address here, then click on "register" to commit: (We do not expect more than a few messages a year on this list.)

Our Packages

gfun - generating functions package

The gfun package is used for the manipulation and discovery of generating functions. Written by Bruno Salvy, Paul Zimmermann and Eithne Murray. Contact: gfun@inria.fr.

It has its own site that you might want to check for the most recent version and many real-life examples.

Mgfun - multivariate generating functions package

The Mgfun package is intended for calculations with multivariate generating functions, in particular for their symbolic summation and integration, and for the proof of special function and combinatorial identities. It also allows operations in non-commutative algebras of operators (such as Weyl or Ore algebras), elimination in these algebras, and operations on holonomic functions. In particular, the subpackages Ore_algebra and Groebner have been incorporated into the core library of MapleV Release 5, as a replacement for the former grobner package. The whole set of packages is part of the algolib library. Written by Frédéric Chyzak.

regexpcount - regular expressions and counting

Regexpcount is a package dedicated to regular expressions and automatas described in the combstruct syntax; in the case of automatas, this facilitates translation to generating functions. Regexpcount provides also access to the internal structures of automatas described as maple tables. When counting the number of occurrences of motifs or regular expressions in random sequences, the underlying probabilistic model of the sequences is Bernoulli or Markov.

gdev - series expansion and limits

A facility for more general series expansions and limits. Uses a different model for asymptotic series expansions than Maple's asympt and series commands. Includes the equivalent function mentioned in the survey article. equivalent does asymptotic expansion of Taylor coefficients, useful in the study of generating functions. Written by Bruno Salvy.

introduction - an introduction to the gdev functions, including examples.
Download gdev as part of the algolib library.
papers - papers written about gdev

AUTOMATIC ASYMPTOTIC AVERAGE-CASE ANALYSIS OF ALGORITHMS

luo - system for the analysis of algorithms

A system written in Caml and Maple to perform average-case complexity analysis of algorithms. Written by Bruno Salvy and Paul Zimmermann. Contact: algolib@inria.fr.

introduction - an introduction to the luo system.
code - to reach the code.
papers - papers written about luo

Note that a lot of LUO has been incorporated and modernized in the combstruct package, so you might want to check there first.