[Next] [Contents]

## Introduction

`MuPAD-Combinat` is an open-source algebraic combinatorics package for the computer algebra system MuPAD 2.0.0 and higher. The main purpose of this package is to provide an extensible toolbox for computer exploration. The development started in spring 2001, and the package currently contains functions to deal with usual combinatorial classes (partitions, tableaux, decomposable classes, ...), Schubert polynomials, characters of the symmetric group, and weighted automata. It supplies the user with tools for constructing new combinatorial classes and combinatorial algebras and, as an application, provides some well-known combinatorial algebras like the algebra of symmetric functions and various generalizations. This represents about 65000 lines of MuPAD and C++ code together with 350 pages of doc, written by 3 main developers and altogether about 20 contributers. The core of the package is integrated in the official library of MuPAD since version 2.5.0.

The purpose of this paper is to present the package for people that can be interested as more or less advanced users but also for people who may contribute code and for developers that does not knows about MuPAD but that want to compare the package with other similar packages.

After a presentation of our motivation to write such a package, we propose a guided tour to the package. Though this tour suppose some familiarities with the MuPAD computer algebra system, the first part describe the combinatorial feature of `MuPAD-Combinat` and is intended for users. It does not suppose strong programming knowledges. The second part of the tour devoted to the building of new combinatorial algebras, is a little bit more advanced.

After that, the paper goes on with some design notes for the `MuPAD-Combinat` package. This third part of the paper deals much more with programming technics, and may interest people who wants to understand inner mechanisms of the package. Note that this part is not only written for peoples who want to contribute but also to people who want to know the internal mechanism of `MuPAD-Combinat`, for example to compare it with similar package. It requires strong knowledge about programming but not necessarily about the MuPAD language itself. In particular we discuss the advantage of using typing mechanism and object oriented features rather that just manipulating expressions which is the usual mechanism of similar packages. As such, it may interest people wanting to have comparable feature in a different language.

### A need for a toolbox for computer exploration in algebraic combinatorics

While doing research in (algebraic) combinatorics, computer exploration can be of great help. In its simplest form, when looking for the generating series of a combinatorial class, one can try to compute its first terms; those may give a hint on a recurrence relation or a general formula; at least, they can be sent to the Online Encyclopedia of Integer Sequences [Sloane] for comparison with other well known sequences. In general, using a computer allows for studying large scale examples (in combinatorics, the size of the examples usually grows very quickly!). This can help to suggest conjectures, check them for likeliness, or find counter-examples.

The first author is interested in symmetric functions and their generalizations in connection with representation theory. The problem is basically to find interesting bases together with product and change of basis rules (analogues of Littlewood-Richardson rules). His results were mainly obtained by computer exploration, using some `Maple` routines extending the `ACE` package. Similarly, the second author had developed a library for computing within invariant rings of permutation groups, in order to study certain invariant rings related to graph theory. The common point of those tools was that they essentially consisted of basic combinatorial routines together with mechanics to compute within certain combinatorial algebras.

By a combinatorial algebra, we mean a vector space, with a basis indexed by combinatorial objects, and endowed with a product that obeys some combinatorial rule. Think of the algebra of the n-th symmetric group: the basis is indexed by permutations, while the product is given by the usual product of permutations. Such combinatorial algebras appear in many situations (mac-donald, NCSF, Peaks). One often needs to run computations within such algebras, for example for finding generators, idempotents, or better understanding their algebraic structure.

A typical computation is to find the elements c in a given combinatorial algebra satisfying certain properties (say c2=c):

1. Provide the product rule on basis elements (unless the algebra is already implemented);
2. Produce a system of equations characterizing those elements c by running appropriate computations in the algebra;
3. Solve this system of equations;
4. Interpret the result.

This simple example highlights what the platform for computer exploration should essentially provide: in the first step it helps to have right under hand a wide toolbox of basic combinatorial routines; in the second step, the system should take care of all the linear bookkeeping to allow for manipulating elements of the algebra; the third step requires all the usual computer algebra tools (linear algebra, Gröbner bases, integration, solvers, ...). We do not plan to automatize step 4.

### Review of preexisting software

We now review some related algebraic combinatorics software, and describe to which extent they did or did not fit our needs. We do not seek completeness, but rather want to present the background that motivated the definition of the specifications for `MuPAD-Combinat`. For a complete list of related software, we refer to `http://www.mat.univie.ac.at/ slc/divers/software.html`.

One of the first, and most famous, package for algebraic combinatorics is J. Stembridge's `SF` library for `Maple` which allows to compute with symmetric functions.

A more ambitious package for `Maple`, called `ACE`, was developed in Marne-la-Vallée, mostly by S. Veigneau. It provides a wide range of combinatorial routines and implements several classical combinatorial algebras (symmetric functions, quasi-symmetric function, non commutative symmetric functions, Schubert polynomials, ...) using state of the art algorithms. Being a library for a computer algebra system that is widely used in the community helped it to spread (there are about 100 known users), and allowed to combine it with the many other existing combinatorics package for the same system. On the other hand it suffered from the poor programming language of `Maple`, and the continuous incompatibilities with the new versions of `Maple`made its maintenance tricky. Also, it appeared with time that the overall design made it difficult to extend in particular for defining new combinatorial algebras. Altogether, the development essentially stalled in 1999 when S. Veigneau left for industry after his PhD thesis.

`mu-EC`, also developed in Marne-la-Vallée by V. Prosper, was an attempt to translate `ACE` for the computer algebra system MuPAD. The goal was mainly to try if the programing language was more adapted to the needs, and in particular to incorporate Symmetrica (see below) into the system, via a dynamic module. However, it suffered from the same design and development model limitations than ACE and the development also stalled when V. Prosper left for industry after his PhD thesis in 2000.

A. Kohnert leads the development of `Symmetrica`, a collection of `C` routines to compute with symmetric functions and Schubert polynomials, ordinary, modular, and projective representations of the symmetric group, and Hecke algebras of type A. The underlying programming language allows very substantial speed improvements compared to equivalent algorithms written, say, in `Maple`. The object oriented design definitely helps for maintaining and extending it. On the other hand, it does not provide support for easy definition of new combinatorial algebras, and can't be straightforwardly combined with other computer algebra tools. The remaining drawbacks, coming from the programming language, are partly matters of personal taste. There is a steep learning curve for non everyday programmers, which makes it difficult to attract new users. We also find the development cycle to be too long in a low-level programing language. Finally, not having an interpreter makes it quite unpractical for interactive computer exploration (this could be circumvented by using a `C` interpreter like ).

B. Weybourne also wrote an interactive program called `Schur` for calculating properties of Lie groups and symmetric functions, with a view toward physics. As for `Symmetrica`, it can't be easily combined with other computer algebra tools, and does not provide support for easy definition of new combinatorial algebras.

To some extent, the systems and allow for defining new combinatorial algebras, and provide a wide set of tools from group theory and algebra that are useful for algebraic combinatorics. We discuss them further later on in the choice of the underlying system.

Finally, one should mention the `Maple` library for Gröbner basis computations by F. Chyzak which allows to easily implement those combinatorial algebras that fit within the more specific framework of Ore-algebras.

### Specifications

As argued in the former sections our goal is to have a flexible and easy to use toolbox for computer exploration in algebraic combinatorics. This means two distinguished and closely interfaced set of packages: A first for combinatorics a second for algebra. The combinatorial part should provide the basic routines to deals with various combinatorial objects. As such, it has to be a large collection of many various relatively small functions to count, list, manipulate combinatorial objects. Most of the required combinatorial utilities are quite common (say, list all the partitions of a given integer, ...); however, there are so many potential common utilities that a combinatorial package will never be able to provide all of them, or at least not in an optimized form.

In our minds, such a package is written when needed in research. So the main goal here is to share the code. Thus it must be easy to add some functions in the package, and each functions should have a natural and easy to find place in the package. Such a package should make it easy to integrate new utilities by providing a well designed framework. Ideally, the package should act as a repository where users would include their utilities while they develop them for their own needs. Furthermore, the package should provide versatile tools that makes it easy to define new combinatorial classes, new algebras, and so on.

The algebraic part should be a sort of mecano build on top of the combinatorial part. On the contrary to other package like `ACE` ore `Symmetrica`, we wanted to have a unspecialized, very flexible and extensible package to build algebraic objects. Standard algebras such as symmetric functions are given as examples rather than as goal. We believe than what is needed is more a toolbox than a set of polished implementation of various algebras. So the package should take care about all tedious part of computations such has parsing, extracting coefficients, converting to vector notations, .... Hence, the writer can concentrate on the specific part of his problem which is, most of the time in our experience, in combinatorics.

Moreover, the system should allows to ask very natural question such as for example the rank of a set of vector or which element in a combinatorial algebra are idempotents. In such computations, one builds large systems of equation, linear or not. To solve such systems, one often needs general computer algebra tools, like linear algebra, integration, Gröbner basis, and so on. Interfacing with such tools should be as seamless as possible. So we choose to use a generic computer algebra system. But as the size of the equation system may be very large, we often needs more specialized packages. Thus we need to be able to interface as easily as possible our package with other one such as `gb`, `alp`, ....

As a guideline for choosing what has to be done, we decided to take to following rules:

Our ultimate goal is to do research, not to write software. However, to do this research, we need the appropriate tools. Hopefully, in the middle term, sharing those tools and the associated development time with others is a way for us to save time for more research. So the goal is to share as much and as earlier as possible pieces of codes. This implies that, the development cycle ought to be short. To stress on this, here is the schedule of one of our (ideal) research days:

10:00
  Conjecture A is on the board;
10:10
  We have a first idea on how to test it on a computer
10:30
  The code is written; the laptop starts computing
10:31
  The first results are there; oops, a counter-example; the conjecture is indeed incorrect as it is;
10:45
  A patched conjecture A' is formulated;
10:46
  The laptop starts running the adapted code;
10:50
  The first results are there; ok, maybe this conjecture is not so stupid after all; let us try to prove it;
11:30
  More results are there; but memory is running low on my laptop. Hey, see? All coefficients are integers. This gives a good hint for the proof. But this also suggests a much better algorithm for running the computation.
12:30
  The new code is written. Good, it runs 10 times faster, and uses far less memory. Let us start it on the server, and go for lunch.
14:00
  Back from lunch; many more examples have been checked in the meantime.
15:00
  Conjecture A' is proved; problem B(A') is on the board. the server is computing some examples overnight.
17:00
  The code written during the day is analyzed; the bits that can be reused are cleaned up and integrated into `MuPAD-Combinat` together with documentation and test files; everything is instantly available on the anonymous CVS server on `mupad-combinat.sf.net`.

Genericity, flexibility, rapid prototyping, and speed of development are at a premium. Of course, efficiency is desirable but constant time factors are not necessarily so important (anyway, most of the time, the size of the studied objects grows exponentially). Optimizations are usually only really required in very specific parts (underlying linear algebra, ...); only those parts need to be optimized, after a careful analysis with a profiler. Of course, ideally, the code should be written in such a way to leave room for such specializations and optimizations. All of this speaks for a high-level language that allows to write code that sticks as much as possible to the mathematical way of thinking. Of course, this does not preclude the use of some modules written in a low-level language like C for the critical sections, when there is a clear need for it.

Following the goal to share work as possible, the package should allow different levels of use:

- Occasional usage, as a mere calculator using only predefined utilities.
- Regular usage, programming of little utilities, definition of simple new combinatorial classes and algebras;
- Intensive usage, programming of complete libraries for new combinatorial classes and algebras;
- Core hacking, implementation of generic algorithm, writing of external modules (say in C) for optimized speed, ...

And finally, being integrated in a well-known and widely available system helps so that the user can work in his usual environment; this is particularly important for the first two levels of usage above. Moreover, this is a critical problem to share code.

### Structure of this document

Apart from the preceding introduction this paper is divided in two sections. The First section is a guided tour trough `MuPAD-Combinat`. After a general example of usage, we describe step by step the structure of a combinatorial class, together with two generic tools to deals with constrained list of integers and grammar described decomposable objects. We gives then some examples, how to define new combinatorial classes. The next two subsection are devoted to combinatorial algebras, predefined and new one. This first part ends with a summary of what is now provided in the package and what should be in the short term. Note that the version of this document included in the `MuPAD-Combinat` documentation provides exercises throughout the guided tour.

The second section is devoted to the design of the package. First we discuss about some very basic conventions such as naming. Then we deals with combinatorial objects and how they can be represented in a computer algebra system. We describe our solution to have a unified interface for various combinatorial classes on the top of which we will build algebraic object. In particular, inheritance allows here to standardize and reuse code. Finally, we deals with combinatorial algebras. We describe the advantage of typing objects rather that using expressions. Then we concentrate on the description of several implementation of free module and how the system take care of linearity. We ends by the description of combinatorial algebra with different bases and the way the system deals with the conversion between these different bases. The suggested order of reading is to browse quickly through the guided tour (Section [>>]), and the design notes (Section [>>], essentially the beginning of subsections [>>] Representing combinatorial objects and classes and [>>] Representing combinatorial algebras), and then to read those two sections in detail with a computer under hand to experiment with the examples.

[Next] [Contents]

MuPAD Combinat, an open source algebraic combinatorics package