We construct the free module over the rational numbers with basis indexed by integer partitions:

An element of F can be seen as a formal linear combination of partitions. We create such a linear combination:

The B just stands for the name of the basis. This is customizable by changing the value of the entry "basisName". Further control on the output is possible but not yet fully documented.

Most of the usual "polynomial" methods are available:

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.

There are in fact different possible implementations for Dom::FreeModule without a clear cut advantage of one over the others (as a parallel, in C++ there exists two implementations of association tables: map using sorted lists and hash_map using hash tables). So, in fact, several implementations are available which use different internal data representations: Dom::FreeModulePoly, Dom::FreeModuleList, and Dom::FreeModuleTable. By default, Dom::FreeModule is an alias for Dom::FreeModulePoly. All those implementations are in the category 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 Dom::FreeModule(R, Basis).

In this example, we review quickly those three implementations. In the Dom::FreeModuleTable implementation, an element x is stored as an association table (DOM_TABLE). For example, here is the internal representation of the element x above:

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.

In the Dom::FreeModulePoly implementation, elements are is stored using kernel polynomial (DOM_POLY). Those kernel polynomial objects of MuPAD (domain 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 Dom::Matrix) use univariate polynomials internally as internal representation for sparse column vectors. Here is the internal representation of the element x above:

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 ). Otherwise, the user may provide a pair of functions rank and unrank that does the conversions. By default, the system creates a dummy pair of such functions: the rank function associate in turn the numbers 1,2,3,... to each new object it encounters. For example, the rank of [3,2,1], [5,2], and [5,3,1] above are respectively 1,2, and 3. This corresponds to the order in which the corresponding elements of F have been created.

This representation is very fast for linear algebra operations. Furthermore, if univariate polynomials are used with the variable _X (this is the default), the data structure coincides exactly with the one used by 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 x is logarithmic in the number of terms of 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.

The last implementation 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 Dom::FreeModule since 1997. For example, here is the representation of the element x above:

Obviously, there needs to be an order on the basis elements (C should be a Cat::OrderedSet). Accessing a leading or trailing term is constant-time; accessing the coefficient of a given term in x is logarithmic in the number of terms of x.