[Previous] [Next] [Contents]

## `Dom::FreeModule` -- the domains of free modules

#### Introduction

``Dom::FreeModule`(R,C)` creates the free module over the coefficient ring `R` with basis indexed by the combinatorial class `C`.

#### Domain

`Dom::FreeModule(R)`

#### Parameters

`R` | - | a ring, i.e. a domain of category `Cat::Ring`.
`C` | - | a combinatorial class, i.e. a domain of category `Cat::CombinatorialClass`.

#### Categories

`Cat::ModuleWithBasis(R)`

#### Details

- ``Dom::FreeModule`(R,C)` creates the free module over the coefficient ring `R` with basis indexed by the combinatorial class `C`.

- Formally, this is the set of the functions from `C` to `R` which are zero except on a finite number of elements of `C`; this set is a free module over `R` (or a vector space if `R` is a field). Its elements can be seen as formal finite linear combinations of elements of `C`.

- This is the prototypical instantiation of the category `Cat::ModuleWithBasis(.)` See the documentation of this category for the methods available.

#### Example 1

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

    >> F := Dom::FreeModule(Dom::Rational, combinat::partitions)

             Dom::FreeModulePoly(Dom::Rational, combinat::partitions)

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

    >> x := F([3, 2, 1]) + 4*F([5, 2]) + 1/2*F([5, 3, 1])

                   1/2 B([5, 3, 1]) + 4 B([5, 2]) + B([3, 2, 1])

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:

    >> nterms(x)

                                         3

    >> F::support(x)

                          [[5, 3, 1], [5, 2], [3, 2, 1]]

    >> F::terms(x)

                      [B([5, 3, 1]), B([5, 2]), B([3, 2, 1])]

    >> F::monomials(x)

                   [1/2 B([5, 3, 1]), 4 B([5, 2]), B([3, 2, 1])]

    >> F::coeffs(x)

                                    [1/2, 4, 1]

    >> F::lterm(x)

                                   B([5, 3, 1])

    >> F::lcoeff(x)

                                        1/2

    >> F::tterm(x)

                                   B([3, 2, 1])

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.

#### Example 2

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:

    >> F := Dom::FreeModuleTable(Dom::Rational, combinat::partitions):
       x := F([3, 2, 1]) + 4*F([5, 2]) + 1/2*F([5, 3, 1]):
       extop(x)

                                table(
                                  [5, 3, 1] = 1/2,
                                  [5, 2] = 4,
                                  [3, 2, 1] = 1
                                )

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:

    >> F := Dom::FreeModulePoly(Dom::Rational, combinat::partitions):
       x := F([3, 2, 1]) + 4*F([5, 2]) + 1/2*F([5, 3, 1]):
       extop(x)

                                    3       2
                         poly(1/2 _X  + 4 _X  + _X, [_X])

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, ...). 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:

    >> F := Dom::FreeModuleList(Dom::Rational, combinat::partitions):
       x := F([3, 2, 1]) + 4*F([5, 2]) + 1/2*F([5, 3, 1]):
       extop(x)

                  [[1/2, [5, 3, 1]], [4, [5, 2]], [1, [3, 2, 1]]]

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`.

#### Changes

- `Dom::FreeModule` is a new domain. It provides all the functionnalities of the former (undocumented) `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 `Dom::FreeModule` has been temporarily renamed into `Dom::FreeModuleOld`.

[Previous] [Next] [Contents]

MuPAD Combinat, an open source algebraic combinatorics package