Dom::FreeModule
--
the domains of free modules
creates the free module over the
coefficient ring Dom::FreeModule
(R,C)R
with basis indexed by the combinatorial
class C
.
Dom::FreeModule(R)
R | - | a ring, i.e. a domain of category Cat::Ring . |
C | - | a combinatorial class, i.e. a domain of category
Cat::CombinatorialClass . |
Cat::ModuleWithBasis(R)
Dom::FreeModule
(R,C)
creates the free module over the
coefficient ring R
with basis indexed by the combinatorial
class C
.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
.Cat::ModuleWithBasis(.)
See the documentation of this
category for the methods available.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.
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
.
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
.
MuPAD Combinat, an open source algebraic combinatorics package