% $Id: motivations.tex,v 1.1.1.1 2003/09/15 16:37:35 nthiery Exp $
\section{Motivations, history and status}

\subsection{Combinatorics and Algebra}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\emph{"Laplace discovered the remarkable correspondence between set
  theoretic operations and operations on formal power series, and put
  it to great use to solve a variety of combinatorial problems"}. --
Gian-Carlo Rota~\cite{Rota.FOC}

% Finite operator calculus Academic press 1975

The intervention of algebra in combinatorics came very early. For
example, the basic tools of formal power series allow to easily compute
using the complicated recurrence relations that appear when
counting combinatorial objects. In the same spirit, a classical
approach to count objects with symmetries is to break those symmetries
by putting labels on the parts of the object; then there is a group
acting on the labels, and the problem is reduced to compute the number
of orbits under the action of this group. This is the classical method
of Pólya enumeration, which is treated extensively in A.~Kerber's book
"Algebraic combinatorics via finite group actions"~\cite{Kerber.ACF}.

Conversely, in modern algebra, classification problems in group
theory or representation theory, have given rise to many
constructions (should we say algorithms ?) of algebraic objects from
combinatorial inputs such as partitions, Young diagrams, Dynkin
diagrams, finite oriented graphs (also known as \emph{quivers}).

In both cases, there is a strong need to compute within
\emph{combinatorial algebras} (that is algebraic structures, such as
vectors spaces or algebras, whose bases are indexed by combinatorial
objects).

%\subsubsection*{Combinatorial (Hopf) Algebra}

One of the first and most fundamental object in algebraic
combinatorics is the algebra of symmetric functions. This was first
understood by Mac-Mahon, who can be seen as the father of modern
algebraic combinatoric. The interest of the algebra of symmetric
functions comes from its extremely rich algebraic structure, starting
from the fact that it is not only an algebra but also a Hopf algebra.
Recall that a \emph{Hopf algebra} is an algebra whose linear dual is
also an algebra, with some compatibility between these two structures;
essentially, there is an extra "decomposition law". The importance of
Hopf algebras in combinatorics was perhaps first stressed by
G.-C.~Rota who pointed out how many combinatorial objects naturally
possess a Hopf structure, because they can be composed and
decomposed~\cite{Joni_Rota.1979}. In fact, under this combinatorial
Hopf structure, many things that we would like to count transform
naturally, yielding new tools in combinatorics. The study of symmetric
functions was the starting point of a domain of combinatorics which is
devoted to the study of combinatorial Hopf algebras. This is a rapidly
growing
field~\cite{Reutenaueur.1993,Hoffman.2002,Duchamp_Hivert_Thibon.2002},
and it has applications in many different areas, such as
representation theory of quantum groups in
mathematics~\cite{Chari_Pressley.1995,Majid.2002}, and renormalization
of quantum fields in
physics~\cite{Connes_Kreimer.1998,Kreimer.1998,Broadhurst_Kreimer.1999}.


\subsection{The birth of \texttt{MuPAD-Combinat}}

\subsubsection*{An itch to scratch}

We (F.~Hivert and N.~M.~Thiéry) had both written relatively large
pieces of code for our own computations and discovered, \emph{a
  posteriori}, that the core tools of our libraries were essentially
the same. Furthermore, several excellent packages we used, like \ace,
\muec{} or \cs, were slowly dying out by lack of proper maintenance and
distribution.

So, we decided to put our work in common and, in order to avoid as
much as possible the \emph{Yet Another Combinatorial Package (tm)}
effect, we tried to analyze the situation. Basically, here are some of
the problems we face:

\begin{itemize}
\item There are too many potential platforms for combinatorics (Maple,
  Mathematica, MuPAD, GAP, Magma, Axiom, Aldor, ...), with little
  tools for exchanges between them (so far, will Open Math save us one
  day ?). All those platforms have advantages, and all of them have
  drawbacks: no open source, expensive, not widely available, too
  specialized, \emph{very} bad programming language, ...
\item Existing packages for algebraic combinatorics are designed to
  compute efficiently with specific algebras. However, they are not
  easily extensible because they do not provide tools to construct new
  combinatorial algebras.
\item There is a lack of communication and software exchange in the
  community: too many things get \emph{reimplemented} over and over.
  Many little pieces of code just stay in users home directories
  without being \emph{integrated}, \emph{distributed} and
  \emph{reused}.
\item The long term \emph{software maintenance} is sloppy: often a
  package is developed by a student, which then leaves for other
  skies. Shortly the package gets incompatible with the next version
  of the platform, and finishes in the trash bin.
\end{itemize}

\subsubsection*{An opportunity}

Some time ago, N.~M.~Thiéry had made contacts with the \mupad{} group,
in order to integrate his library \permuvar, or parts of it, to the
official release of \mupad{}. This library contained several
combinatorial routines, and he suggested some reorganization of the
(rather minimal) combinat package of \mupad{}, in order to ensure a
better integration. His offer was warmly welcome, and the \mupad{}
group actually decided to make him the official maintainer of the
\texttt{combinat library}, with full freedom for reorganizing and
expanding it.

% Sometimes we would like to have more static checks

Is \mupad{} the best platform for our needs? Technically, it has
proved so far to be reasonably adapted to our requirements. The
language is quite clean, and seems to scale properly as the package is
growing. Most important, the collaboration with the \mupad{} team is
working smoothly; in particular they have been open-minded with
respect to our (numerous) suggestions of improvements, including some
sensitive kernel changes to polish the semantic of domains.

On the other hand, \mupad{} is not open-source. We are not happy with
this situation, and actively negotiate with them about this; for
example, the recent release of the \mupad{} library under an open
source license was a precondition we had set for the inclusion of
\mupadcombinat{} in this library. Our impression is that they are, in
theory, very favorable to open-source principles; however, in
practice, they judge that they could not currently release the
\mupad{} kernel under an open-source license without putting their
very survival at great risks.

\subsubsection*{Development model and plan}

Our bet is that what is needed above all is a \emph{good development
  model}\/. Ideally, such a package ought to be developed by a
community, not just by one person or by one lab. We want to see how
well the open-source development model can apply to the Algebraic
Combinatorics community. The choice of open-source itself is obvious;
however it is not clear whether the principles that made the success of
general interest community-developed open-source software will apply
because the targeted audience is relatively small. The main challenge
is to reach quickly the critical mass above which the package will
attract users and developers, and will grow on its own by the users
contributions.  To this end,
\begin{itemize}
\item Can we integrate other developers ?
\item Can we integrate other packages ?
\item Can we interface with other software ?
\end{itemize}
The point is \emph{not} to take the control of other packages. It is
just to drop a little bit of glue between packages to help them
cooperate together.

Anyway, the plan is to quickly extend the features of \mupadcombinat,
while keeping it clean, organized, stable, and well documented. To
this end, the core developers concentrate on the following:
\begin{itemize}
\item Provide a sane framework, where external software can easily be
  integrated;
\item Maintain the package, make it easy to install, ...
\item Coordinate the contributions, and provide support to those who
  wish to contribute.
\end{itemize}
The real coding work ought to be done by users, so \emph{we need your
  help}! See the web page \url{http://mupad-combinat.sf.net} for how
you can contribute.

Note that there are many features that are not yet completely
documented, or that would be trivial to add in a very short amount of
time. So, if you miss a specific feature to get started, please feel
free to ask for it. We are ready to invest some time in helping out
new users: hopefully they will become future contributers. In general,
we really are looking for feedback.



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