The objective of the library alp1
is to provide a framework for symbolic and numeric
computations. It allows to define parameterised
but efficient classes of basic algebraic objects such as vectors, matrices,
monomials and polynomials, ...which can be used easily in the construction
of more elaborated algorithms. We pay a special attention to genericity or
more precisely to parameterised classes (templates) which allow us to tune
easily the data-structure to the problem to be solved. So called template expression are used to guide the expansion of code during the
compilation and thus to get very efficient implementations. We also consider
carefully the problem of reusability of external libraries. Currently, we
have connected lapack (fortran library for numerical linear algebra),
umfpack, SparseLib (respectively fortan and C++ libraries for sparse
matrices), superlu (C library for solving sparse linear system), gmp (C library for extended arithmetics), GB, RS, ...Thus,
specialised implementation for instance using lapack routines, can
coexist with generic one, the choice being determined by the internal
representation. We also want this library to be easy to use. Once the
basic objects have been defined by specialisation of the parameters, including
maybe the optimisation of some critical routines, we want
to be able to write the code of an algorithm ``as it is on the paper''. The
polymorphism and genericity of C++ allows us to work in this direction.
We have distinguished three levels of structure, implemented either as
classes or namespaces: containers, views and modules.
They specify the internal representation of the objects. They
provide methods or functions for accessing, creating, transforming
this representation and thus depend on the data-structure. They are implemented
as classes (often parameterised by coefficient types or index types), with
few functions so that they can be rewritten or extended easily.
We follow the approach of the stl library [STL96], which implements
basic structures such as list<R>, vector<R>, set<R>, deque<R>,
... New containers have been added such as one-dimensional arrays
array1d<C> with generic coefficients, two-dimensional arrays
array2d<C> for dense matrices, lapack<C> for the
connection to Lapack library, sparselu<C> for
the connection to SuperLU, ...
They specify how to manipulate or to see the containers as
mathematical objects and provide operations on the objects which are
independent of the container. They are implemented as classes
parameterised by the container type and sometimes by trait classes
which precise the implementation. The only data available in such a class,
called rep, is of container type.
For instance a one-dimensional array of double numbers
can be seen as a vector, using the type
VectStd<array1d<double> >.
Among the operations defined in this class, we have
for example, the vector operators +=, -=, +, - and the scalar
multiplications *, *=.
But such an array can also be viewed as a univariate polynomial. In this
case, we will define the following type :
UPolyDense<array1d<double> >
which extends the operations given in VectStd<array1d<double> >
by adding the polynomial multiplication operators *=, * and
changing the output operator.
The implementations of these views are defined in a module
and can easily be specialised (see next section).
Here are the main examples of view classes that are implemented in the
current version of the library, R standing for the container type:
VectStd<R> (standard vectors), MatDense<R> (dense
matrices), MatStruct<R> (structured matrices), MatSparse<R>
(sparse matrices),
UPolyDense<R> (dense univariate polynomials),
UPolyQuot<R> (quotiented univariate polynomials),
Monom<C,E> (monomials with coefficients in C and
exponents in E),
MPoly<R,O> (multivariate polynomials where O defines
the order on the monomials).
A module is a collection of implementations which apply
to a family of objects sharing common properties (such as vectors, matrices,
univariate polynomials, ...). They are implemented as namespaces
and thus can be extended easily. They are used to define generic
implementations.
For instance in the module (or namespace) VECTOR, we have
gathered generic implementations for vectors independent of the internal
representation, such as Print, Norm, ...
The main modules of the library are VECTOR, MATRIX,
LINALG (linear algebra implementations),
UPOLYNOMIAL (univariate polynomials),
MPOLYNOMIAL (multivariate polynomials).
As explained before, we need to be able to specialise some critical
functions of our classes. For the univariate polynomials
UPolyDense<array1d<C> >, we would like for instance, to replace the naive
multiplication by a more efficient one, based eg. on fft.
This can be done easily by extending the namespace UPOLYNOMIAL and
by defining the function:
template<class C>
void UPOLYNOMIAL::mult(array1d<C> & r, array1d<C> & a, const array1d<C> & b) {...}
- 1
- http://www.inria.fr/saga/logiciels/ALP/