% $Id: preface.tex.save,v 1.1.1.1 2004/10/04 17:25:14 nthiery Exp $

% The links created by mh2html are buggy for references like
% \Mup[PART,]{muEC::PART}. The following definition just
% calls Mup in latex but is ignored by mh2html which uses the
% definition at the end of mh2html.def

\begin{Mnohtml}
  \gdef\myMup#1#2{\Mup[#1,]{#2}}
\end{Mnohtml}

\newcommand{\cpp}{\href{http://www.research.att.com/~bs/C++.html}{\texttt{C++}}}
\newcommand{\cppref}{\cpp{}}
\newcommand{\cint}{\href{http://root.cern.ch/root/Cint.html}{\texttt{CINT}}}
\newcommand{\cintref}{\cint{}}
\newcommand{\java}{\href{http://java.sun.com/}{\texttt{Java}}}
\newcommand{\javaref}{\java{}}
\newcommand{\caml}{\href{http://caml.inria.fr/}{\texttt{Caml}}}
\newcommand{\camlref}{\caml{}}

\newcommand{\maple}{\href{http://www.maplesoft.com/}{\texttt{Maple}}}
\newcommand{\mapleref}{\maple~\cite{Char_al.MRM}}
\newcommand{\mathematica}{\href{http://www.wolfram.com/}{\texttt{Mathematica}}}
\newcommand{\mathematicaref}{\mathematica{}~\cite{Mathematica}}
\newcommand{\maxima}{\href{http://maxima.sourceforge.net/}{\texttt{Maxima}}}
\newcommand{\maximaref}{\maxima{}}
\newcommand{\axiom}{\href{http://www.nongnu.org/axiom/}{\texttt{Axiom}}}
\newcommand{\axiomref}{\axiom{}~\cite{Axiom}}
\newcommand{\aldor}{\href{http://www.aldor.org/}{\texttt{Aldor}}}
\newcommand{\aldorref}{\aldor{}~\cite{Aldor}}
\newcommand{\gap}{\href{http://www-history.mcs.st-and.ac.uk/~gap/}{\texttt{GAP}}}
\newcommand{\gapref}{\gap~\cite{GAP4}}
\newcommand{\magma}{\href{http://www.maths.usyd.edu.au:8000/u/magma/}{\texttt{Magma}}}
\newcommand{\magmaref}{\magma~\cite{Cannon_al.1996,Wieb_al.1997}}

\newcommand{\ace}{\href{http://phalanstere.univ-mlv.fr/~ace/}{\texttt{ACE}}}
\newcommand{\aceref}{\ace~\cite{ACE}}
\newcommand{\muec}{\href{http://phalanstere.univ-mlv.fr/~muec/}{\texttt{$\mu$-EC}}}
\newcommand{\muecref}{\muec{}~\cite{muEC}}
\newcommand{\symmetrica}{\href{http://www.mathe2.uni-bayreuth.de/axel/symneu_engl.html}{\texttt{Symmetrica}}}
\newcommand{\symmetricaref}{\symmetrica~\cite{SYMMETRICA}}
\newcommand{\ssf}{\texttt{SF}}
\newcommand{\ssfref}{\ssf{}}
\newcommand{\schur}{\texttt{Schur}}
\newcommand{\schurref}{\schur{}}
\newcommand{\mupadcombinat}{\href{http://mupad-combinat.sourceforge.net}{\texttt{MuPAD-Combinat}}}
\newcommand{\mupadcombinatref}{\mupadcombinat{}~\cite{MuPAD-Combinat}}
\newcommand{\permuvar}{\href{http://permuvar.sourceforge.net}{\texttt{PerMuVAR}}}
\newcommand{\permuvarref}{\permuvar{}~\cite{Thiery.PerMuVAR}}
\newcommand{\combstruct}{\texttt{Combstruct}}
\newcommand{\combstructref}{\combstruct{}~\cite{Zimmermann.1994}}
\newcommand{\cs}{\href{http://dept-info.labri.u-bordeaux.fr/~dutour/CS}{\texttt{CS}}}
\newcommand{\csref}{\cs~\cite{Denise_all.1998.CS}}
\newcommand{\molgen}{\href{http://www.mathe2.uni-bayreuth.de/molgen4/}{\texttt{MOLGEN}}}
\newcommand{\molgenref}{\molgen{}}

\newcommand{\linbox}{\href{http://www.linalg.org/}{\texttt{LinBox}}}
\newcommand{\linboxref}{\linbox{}}
\newcommand{\synaps}{\href{http://www-sop.inria.fr/galaad/logiciels/synaps/}{\texttt{SYNAPS}}}
\newcommand{\synapsref}{\synaps{}}
\newcommand{\foc}{\href{http://www-spi.lip6.fr/foc/}{\texttt{FOC}}}
\newcommand{\focref}{\foc{}}

\section{Introduction}

\Malias{combinat}

\mupadcombinat{} 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.  Most of the code derives from
computer exploration while doing research on the following topics:
invariant theory of permutation
groups~\cite{Thiery.IAGR,Thiery.AIG.2000,Thiery.CMGS.2001}, Steenrod
algebras and symmetric functions~\cite{Hivert_Thiery.SA.2002}, binary
tree algebras such as the Loday-Ronco algebra and renormalization in
quantum
electrodynamics~\cite{Hivert_Novelli_Thibon.PBT.2002,Hivert_Novelli_Thibon.PBT.2003},
representation theory, quantum groups, and homological
computations~\cite{Duchamp_Hivert_Thibon.2002}, as well as peaks and
Hecke-Clifford Algebras~\cite{Bergeron_Hivert_Thibon.2003}. This
represents about 65000 lines of MuPAD and C++ code together with 450
pages of documentation, 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.

\medskip

The purpose of this paper is to present the package for novice and
advanced users, for potential contributers, as well as for developers
who do not know about \mupad{} but want to compare the package with
other similar packages.

After a presentation of our motivations for writing such a package, we
propose a guided tour through its features. Though this tour assumes
some familiarity with the \mupad{} computer algebra system, the first
part which describes the combinatorial feature of \mupadcombinat{} is
intended for novice users, and does not assume strong programming
knowledge. The second part of the tour which is devoted to the
building of new combinatorial algebras, is a little bit more involved.

After that, the paper goes on with some design notes. This third part
of the paper deals much more with programming techniques, and may be
of interest for people wanting to understand the underlying mechanisms
of the package, for example to compare it with similar packages. It
assumes some 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 than just manipulating expressions which is the usual mechanism
of similar packages. As such, it may interest people wanting to have
comparable features in a different language.

%\subsubsection{Motivation: some research in algebraic combinatorics}
\subsection{A need for a toolbox for computer exploration in algebraic
  combinatorics}
%\subsubsection{Motivations: computer exploration for research in
%  algebraic combinatorics}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%You may well start with the mathematical fields you wish to explore,

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
\emph{Online Encyclopedia of Integer Sequences}~\cite{Sloane} for
comparison with well known sequences. In general, using a
computer allows one to study large scale examples (in combinatorics,
the size of 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~\cite{Duchamp_Hivert_Thibon.2002}.  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 group 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 (see
e.g.~\cite{MacDonald.SF.1995,Gelfand_Krob_Lascoux_Leclerc_Retakh_Thibon.1995.NCSF1,Connes_Kreimer.1998,Stembridge.peaks.1997}).
One often needs to run computations within such algebras, for example
for finding generators, idempotents, and in general better
understanding their algebraic structure.

A typical problem is to find the elements $c$ in a given combinatorial
algebra satisfying certain properties (say $c^2=c$):
\begin{enumerate}
\item Provide the product rule on basis elements (unless the algebra
  is already implemented);
\item Produce a system of equations characterizing those elements $c$
  by running appropriate computations in the algebra;
\item Solve this system of equations;
\item Interpret the result.
\end{enumerate}
This simple example highlights what a platform for computer
exploration should essentially provide: in step 1, a comprehensive
toolbox of basic combinatorial routines may help to implement the
product rule; in step 2, the system should take care of all the linear
bookkeeping to allow one to easily manipulate elements of the algebra;
step 3 requires all the usual computer algebra tools (linear algebra,
Gröbner bases, integration, solvers, ...).  \ifcolloquial We do not
plan to automatize step 4.\fi

\subsection{Review of preexisting software}

We now review some available software tools for doing algebraic
combinatorics and we comment from our experience and expectations why
or why not, or to what extent, they fit our needs. We do not seek
completeness, but rather want to present the background that motivated
the definition of the specifications for \mupadcombinat{}.  For a
comprehensive list of related software, we refer to
\url{http://www.mat.univie.ac.at/~slc/divers/software.html}.

One of the first and widely known packages for algebraic combinatorics
is J.~Stembridge's \ssfref{} library for \mapleref{} which is designed
to compute with symmetric functions.

A more ambitious package for \mapleref{}, called \aceref{}, 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 one 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 notorious incompatibilities with the new versions of \maple{}
made its maintenance tricky. Experience showed 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 finishing his
PhD thesis.

\muecref{}, 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 test whether the \mupad{} programing language
was more adapted to the needs, and in particular to incorporate
\symmetricaref{} (see below) into the system, via a dynamic
module. However, it suffered from the same design and development
model limitations as \ace{} and the development also stalled when
V.~Prosper left for industry after finishing his PhD thesis in 2000.

A.~Kohnert leads the development of \symmetricaref{}, a collection of
\texttt{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 permits 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 an 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 casual 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 \texttt{C}
interpreter like \cintref{}).

B.~Weybourne also wrote an interactive program called \schurref{} 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 \gapref{} and \magmaref{} allow the user to define
new combinatorial (Lie) 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 one to easily implement those
combinatorial algebras that fit within the more specific framework of
Ore-algebras.

\subsection{Specifications}

\Mnode{specifications}

\subsubsection{A flexible toolbox}

As argued above our goal is to have a flexible and easy to use toolbox
for computer exploration in algebraic combinatorics. This includes two
clearly distinguished but closely interfaced parts: one for
combinatorics and the other for algebra.

\medskip

The combinatorial part should provide basic routines to deal with
various combinatorial objects. As such, it is to become a large
collection of 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,
...) but there are so many potential utilities that a combinatorial
package will never be able to provide all of them, or at least not in
an optimized form. Instead, the aim should be to make it easy for
users to write such utilities as need for them arises. This includes
providing versatile tools for defining and manipulating new
combinatorial classes.

\medskip

The algebraic part should be a sort of mecano built on top of the
combinatorial part. In other packages like \ace{} or \symmetrica{},
the aim is to provide polished implementations of some specific
algebras like symmetric functions. Instead, we aim at providing an
unspecialized, very flexible and extensible toolbox to build new
algebras, with the standard algebras being implemented as mere
examples of applications of the general framework.  In short, the
package should try to take care of the trivial but tedious parts of
the computations, letting the writer concentrate on the specific parts
of his problem which are, most of the time in our experience, of
combinatorial nature.

Moreover, the system should allow for a computation of the answers of
natural questions such as ``what is the rank of this set of vectors?''
or ``which elements in this combinatorial algebra are idempotents?''.
In such computations, one often builds large systems of equations,
linear or not.  Solving such systems, requires versatile general
purpose computer algebra tools, like linear algebra, integration,
Gröbner basis, and so on.  In many occasions, the systems may become
very large, requiring specialized high performance software like, for
example, \href{http://fgbrs.lip6.fr/jcf/index.html}{FGB/RS},
\href{http://www-sop.inria.fr/galaad/logiciels/synaps/}{SYNAPS}, or
\href{http://www.linalg.org/}{LinBox}. Interfacing with such tools
should be as seamless as possible. This speaks for using a general
purpose computer algebra system, that can be easily interfaced with
external specialized tools.

\subsubsection{A short development cycle}

Another aspect of writing software for daily computer exploration is
that the development cycle ought to be short.
\ifcolloquial
To stress on this, here
is the schedule of one of our (ideal) research days:
\begin{itemize}
\item[10:00] Conjecture A is on the board;
\item[10:10] We have a first idea on how to test it on a computer
\item[10:30] The code is written; the laptop starts computing
\item[10:31] The first results are there; oops, a counter-example;
  the conjecture is indeed incorrect as it is;
\item[10:45] A patched conjecture A' is formulated;
\item[10:46] The laptop starts running the adapted code;
\item[10:50] The first results are there; ok, maybe this conjecture
  is not so stupid after all; let us try to prove it;
\item[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.
\item[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.
\item[14:00] Back from lunch; many more examples have been checked
  in the meantime.
\item[15:00] Conjecture A' is proved; problem B(A') is on the board.
  the server is computing some examples overnight.
\item[17:00] The code written during the day is analyzed; the bits
  that can be reused are cleaned up and integrated into
  \mupadcombinat{} together with documentation and test files;
  everything is instantly available on the anonymous CVS server on
  \url{mupad-combinat.sf.net}.
\end{itemize}
\fi%
Here, 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. Ideally, the code
should be written in such a way as to leave room for such
specializations and optimizations.  All of this speaks for a
high-level language that allows one to write code that sticks as much
as possible to the mathematical way of thinking. Of course, this does
not preclude the use of external modules written in a low-level
language like \texttt{C} for the critical sections, when there is a
clear need for it.

\subsubsection{A package designed and developed by users, for users}

The package should allow different levels of use:
\begin{itemize}
\item Occasional usage, as a mere calculator using only predefined
  utilities.
\item Regular usage, programming of little utilities, definition of
  simple new combinatorial classes and algebras;
\item Intensive usage, programming of complete libraries for new
  combinatorial classes and algebras;
\item Core hacking, implementation of generic algorithms, writing of
  optimized external modules (say in C), ...
\end{itemize}
For the first two levels of use, being integrated in a well-known and
widely available system helps so that the user can work in his usual
computing environment. This is crucial to attract new users.

As stressed above, by the very nature of the application field, any
non-trivial usage involves extending the package with new utilities.
To avoid duplicate work, it is essential for users to \emph{share
  their code}. Ideally, the package should essentially end up acting
as a \emph{repository} of user developed routines. To this end, it
needs to define a well designed framework where new utilities can be
easily and quickly integrated in a natural and easy to find place.
Then, defining this framework, and coordinating the developments to
ensure a large scale coherency would be the main role of the core
developers. Of course, the \emph{platform} and the \emph{development
  model} should encourage contributions and foster collaborations.

This aspect is particularly important for us, core developers, as our
ultimate goal is to do research, not to write software. It happens
that, to do this research, we need appropriate tools, and we are
currently investing a lot of energy to launch this project to fulfill
our own needs as well as, hopefully, other's. It is our personal hope
for the near future that sharing those tools and the associated
development time with others will actually save us time for more
research.

\subsection{Structure of this document}

Apart from the preceding introduction this paper is divided into two
sections.  The first section is a guided tour through
\mupadcombinat{}. After a general example of usage, we describe step
by step the structure of a combinatorial class, together with two
generic tools to deal with constrained list of integers and
decomposable objects described by a recursive grammar (this is similar
to the description of languages by context-free grammar, though here
the grammar are not required to be context free). We provide in
particular some examples of how to define new combinatorial classes.
The next two subsection are devoted to combinatorial algebras, both
predefined and new. This first part ends with a summary of the current
and soon-to-be features of the package.  Note that the version of this
document included in the \mupadcombinat{} documentation provides
exercises throughout this guided tour.

The second section is devoted to the design of the package. First we
discuss the choice of the platform and of the development model. We
explain some very basic conventions such as naming. Then we proceed
with combinatorial objects and how they can be represented in a
computer algebra system. We describe the design of a unified interface
for various combinatorial classes on the top of which algebraic
objects can be built. There, inheritance is essential to standardize
and reuse code. Finally, we deal with combinatorial algebras. We
describe the advantage of typing objects rather than using
expressions. Then, we concentrate on the description of several
implementations of free module and how the system takes care of
linearity. We end up by a description of the interface for
combinatorial algebras with different bases and of the mechanism for
conversions between these different bases.  \medskip

The suggested order of reading is to browse quickly through the
\Mhref[index,guidedTour]{guided tour} (Section~\ref{guidedTour}), and
the \Mhref[index,design]{design notes} (Section~\ref{design},
essentially the beginning of subsections
\Mhref[index,designCombinatorialClasses]{\emph{Representing
    combinatorial objects and classes}} and
\Mhref[index,designCombinatorialAlgebras]{\emph{Representing
    combinatorial algebras}}), and then to read these two sections in
detail with a computer under hand to experiment with the examples.


%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
