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.
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):
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 Maplemade 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.
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:
mupad-combinat.sf.net
.
Following the goal to share work as possible, the package should allow different levels of use:
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.
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.
MuPAD Combinat, an open source algebraic combinatorics package