%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% $Id: FreeModule.tex,v 1.1.1.4 2005/01/26 13:42:22 nthiery Exp $
% File:		lib/DOMAINS/DOMAIN/DOC/FreeModule.tex
% Authors:	Nicolas M. Thiéry <nthiery@users.sourceforge.net>
% Purpose:	Documentation for the domain Dom::FreeModule
% Created:	Wed Sep  3 14:54:08 2003
% License:	LGPL
% Project:	MuPAD-Combinat, http://mupad-combinat.sf.net
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{Mhelppage}{FreeModule}{Nicolas M. Thiéry}
  [ImplState=stable,TestState=stable,DocState=stable]
%\Mproofread{...}{...}{...}

\begin{MInfo}
  \eng{the domains of free modules}
  \de{}
\end{MInfo}

\Mproofread{nthiery}{22/09/2003}{}
\Malias{Dom::FreeModulePoly}
\MsetInfoString{Dom::FreeModulePoly}{%
  the domain of free modules, implemented with polynomials}%
\Malias{Dom::FreeModuleList}
\MsetInfoString{Dom::FreeModuleList}{%
  the domain of free modules, implemented with lists}%
\Malias{Dom::FreeModuleTable}
\MsetInfoString{Dom::FreeModuleTable}{%
  the domain of free modules, implemented with tables}%


\begin{MIntro}
  \eng{\Mex{\Mthis{}(R,C)} creates the free module over the
    coefficient ring \Mex{R} with basis indexed by the combinatorial
    class \Mex{C}.}

  \de{}
\end{MIntro}

\begin{MDomConst}
  \MCall{R}
\end{MDomConst}

\begin{MParameters}
 \param{R}
\eng{a ring, i.e. a domain of category \Mup{Cat::Ring}.}
\de{}
 \param{C}
\eng{a combinatorial class, i.e. a domain of category
  \Mup{Cat::CombinatorialClass}.}
\end{MParameters}

\begin{MCategories}
  \Mupc{Cat::ModuleWithBasis}{R}
\end{MCategories}

\begin{MDetails}
  \eng{\Mex{\Mthis{}(R,C)} creates the free module over the
    coefficient ring \Mpar{R} with basis indexed by the combinatorial
    class \Mpar{C}.}
  
  \eng{Formally, this is the set of the functions from \Mpar{C} to
    \Mpar{R} which are zero except on a finite number of elements of
    \Mpar{C}; this set is a free module over \Mpar{R} (or a vector
    space if \Mpar{R} is a field).  Its elements can be seen as formal
    finite linear combinations of elements of \Mex{C}.}
    
  \eng{This is the prototypical instantiation of the category
    \Mup{Cat::ModuleWithBasis}. See the documentation of this
    category for the methods available.}
\end{MDetails}

\begin{MExample}{ex-basic}
  \eng{We construct the free module over the rational numbers with
    basis indexed by integer partitions:}
  \begin{Mexin}
F := Dom::FreeModule(Dom::Rational, combinat::partitions)
  \end{Mexin}
  \begin{Mexout}
   Dom::FreeModulePoly(Dom::Rational, combinat::partitions)
  \end{Mexout}
  \eng{An element of \Mex{F} can be seen as a formal linear
    combination of partitions. We create such a linear combination:}
  \begin{Mexin}
x := F([3, 2, 1]) + 4*F([5, 2]) + 1/2*F([5, 3, 1])
  \end{Mexin}
  \begin{Mexout}
         1/2 B([5, 3, 1]) + 4 B([5, 2]) + B([3, 2, 1])
  \end{Mexout}
  \eng{The \Mex{B} just stands for the name of the basis. This is
    customizable by changing the value of the entry \Mslot{basisName}.
    Further control on the output is possible but not yet fully
    documented. }
  \eng{Most of the usual "polynomial" methods are available:}
  \begin{Mexin}
nterms(x)
  \end{Mexin}
  \begin{Mexout}
                               3
  \end{Mexout}
  \begin{Mexin}
F::support(x)
  \end{Mexin}
  \begin{Mexout}
                [[5, 3, 1], [5, 2], [3, 2, 1]]
  \end{Mexout}
  \begin{Mexin}
F::terms(x)
  \end{Mexin}
  \begin{Mexout}
            [B([5, 3, 1]), B([5, 2]), B([3, 2, 1])]
  \end{Mexout}
  \begin{Mexin}
F::monomials(x)
  \end{Mexin}
  \begin{Mexout}
         [1/2 B([5, 3, 1]), 4 B([5, 2]), B([3, 2, 1])]
  \end{Mexout}
  \begin{Mexin}
F::coeffs(x)
  \end{Mexin}
  \begin{Mexout}
                          [1/2, 4, 1]
  \end{Mexout}
  \begin{Mexin}
F::lterm(x)
  \end{Mexin}
  \begin{Mexout}
                         B([5, 3, 1])
  \end{Mexout}
  \begin{Mexin}
F::lcoeff(x)
  \end{Mexin}
  \begin{Mexout}
                              1/2
  \end{Mexout}
  \begin{Mexin}
F::tterm(x)
  \end{Mexin}
  \begin{Mexout}
                         B([3, 2, 1])
  \end{Mexout}
  \eng{Note that the order between the terms is coherent between the
    different functions. However, by default, this order has no
    particular mathematical meaning, and may even be session
    dependent.}
\end{MExample}

\begin{MExample}{ex-implementations}
  \eng{There are in fact different possible implementations for
    \Mthis{} without a clear cut advantage of one over the others (as
    a parallel, in \texttt{C++} there exists two implementations of
    association tables: \texttt{map} using sorted lists and
    \texttt{hash\_map} using hash tables). So, in fact, several
    implementations are available which use different internal data
    representations: \Mup{Dom::FreeModulePoly},
    \Mup{Dom::FreeModuleList}, and \Mup{Dom::FreeModuleTable}. By
    default, \Mup{Dom::FreeModule} is an alias for
    \Mup{Dom::FreeModulePoly}.  All those implementations are in the
    category \Mup{Cat::ModuleWithBasis} which defines a unified
    interface. So, one can change the underlying implementation at any
    time. Unless you have a specific reason to choose one of the
    implementations, just use the default implementation
    \Mex{Dom::FreeModule(R, Basis)}.}
  
  \eng{In this example, we review quickly those three implementations.
    In the \Mup{Dom::FreeModuleTable} implementation, an element
    \Mex{x} is stored as an association table (\Mup{DOM_TABLE}). For
    example, here is the internal representation of the element
    \Mex{x} above:}
  \begin{Mexin}
F := Dom::FreeModuleTable(Dom::Rational, combinat::partitions):
x := F([3, 2, 1]) + 4*F([5, 2]) + 1/2*F([5, 3, 1]):
extop(x)
  \end{Mexin}
  \begin{Mexout}
                      table(
                        [5, 3, 1] = 1/2,
                        [5, 2] = 4,
                        [3, 2, 1] = 1
                      )
  \end{Mexout}
  \eng{Since any \mupad{} object can be used as index of a table,
    there is no restriction on the basis elements. Also, accessing the
    coefficient of a given term is constant time.}
  
  \eng{In the \Mup{Dom::FreeModulePoly} implementation, elements are
    is stored using kernel polynomial (\Mup{DOM_POLY}). Those kernel
    polynomial objects of \mupad{} (domain \Mup{DOM_POLY}) are stored
    in a sparse non-recursive way using sorted lists of monomials with
    a fixed number of variables. If one forgets about the product,
    this provides a sparse data structure which is both compact in
    memory and very fast for linear operations.  Typically, the
    \mupad{} sparse matrices (domain \Mup{Dom::Matrix}) use univariate
    polynomials internally as internal representation for sparse
    column vectors. Here is the internal representation of the element
    \Mex{x} above:}
  \begin{Mexin}
F := Dom::FreeModulePoly(Dom::Rational, combinat::partitions):
x := F([3, 2, 1]) + 4*F([5, 2]) + 1/2*F([5, 3, 1]):
extop(x)
  \end{Mexin}
  \begin{Mexout}
                      3           2
       poly(1/2 `#_X_`  + 4 `#_X_`  + `#_X_`, [`#_X_`])
  \end{Mexout}
  \eng{To achieve this, one needs to be able to represent an element
    of the basis using an exponent vector (an integer, or a
    fixed-length list of integers). This is trivial when the basis
    readily consists of fixed length lists of integers (integer
    vectors, standard permutations of a given $n$, \dots). Otherwise,
    the user may provide a pair of functions \Mex{rank} and
    \Mex{unrank} that does the conversions. By default, the system
    creates a dummy pair of such functions: the \Mex{rank} function
    associate in turn the numbers \Mex{1,2,3,\Mseq{}} to each new
    object it encounters. For example, the rank of \Mex{[3,2,1]},
    \Mex{[5,2]}, and \Mex{[5,3,1]} above are respectively
    \Mex{1},\Mex{2}, and \Mex{3}. This corresponds to the order in
    which the corresponding elements of \Mex{F} have been created.
    
    This representation is very fast for linear algebra operations.
    Furthermore, if univariate polynomials are used with the variable
    \Mex{_X} (this is the default), the data structure coincides
    exactly with the one used by \Mup{Dom::Matrix}. This allows
    for zero-cost conversions to and from sparse vectors, for doing
    linear algebra.
    
    Accessing the coefficient of a term in an element \Mex{x} is
    logarithmic in the number of terms of \Mex{x} (in the multivariate
    case, with \mupad{} < 3.0.0 this is linear instead of
    logarithmic).
    
    Ranking and unranking is only done for conversions and computing
    other operations like products. In practice, the overhead with the
    dummy implementation seems to be negligible, and largely
    compensated by the fact that most operations deal with short
    integers.}
  
  \eng{The last implementation \Mupc{Dom::FreeModuleList}{R, Basis}
    uses sorted lists internally.  Thanks to Stefan Wehmeier, (Univ.\
    Paderborn) and Werner M.\  Seiler (Univ.\  Karlsruhe), this was
    mostly already implemented in the \mupad{} library, under the name
    \Mex{Dom::FreeModule} since 1997. For example, here is the
    representation of the element \Mex{x} above:}
  \begin{Mexin}
F := Dom::FreeModuleList(Dom::Rational, combinat::partitions):
x := F([3, 2, 1]) + 4*F([5, 2]) + 1/2*F([5, 3, 1]):
extop(x)
  \end{Mexin}
  \begin{Mexout}
        [[1/2, [5, 3, 1]], [4, [5, 2]], [1, [3, 2, 1]]]
  \end{Mexout}
  \eng{Obviously, there needs to be an order on the basis elements
    (\Mex{C} should be a \Mup{Cat::OrderedSet}). Accessing a leading
    or trailing term is constant-time; accessing the coefficient of a
    given term in \Mex{x} is logarithmic in the number of terms of
    \Mex{x}.}
\end{MExample}

\begin{MChanges}
  \version{3.0}%
  \eng[New domain]{\Mthis{} is a new domain. It provides all the
    functionnalities of the former (undocumented)
    \Mup{Dom::FreeModule}, but is not fully backward compatible
    (essentially, the basis is now required to be a combinatorial
    class). To smoothen the transition, the former
    \Mup{Dom::FreeModule} has been temporarily renamed into
    \Mex{Dom::FreeModuleOld}.}
\end{MChanges}

\end{Mhelppage}

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