Boost logo

Glas :

[glas] dense and sparse vectors

From: Toon Knapen (toon.knapen_at_[hidden])
Date: 2005-08-01 08:23:32

Hi all,

Peter Gottschling recently proposed a design for the mathematical
concepts. This is probably rather theoretical but is of course of utmost
importance for a LA library. These concepts are probably easier to
digest once we start using them.

So therefore it's probably time to start introducing some basic
containers. One of the most important goals of GLAS IMHO is having a
generic interface for dense and sparse operations. So therefore I would
like to propose following dense and sparse concepts:

The first family of concepts are the Collections (see The
first member of this family is the Collection itself which basically
defines element-access functionality.

The Collection concept is inherited from by DenseCollection and
SparseCollection. The DenseCollection basically adds the begin() and
end() members to the collection concept. The SparseCollection concept on
the other hand adds iterators over all non-zero's and over all elements.
The members to get the begin and end iterator over all non-zero's are
called nz_begin() and nz_end(), while the the begin and end iterator
over all elements are called all_begin() and all_end(). Note thus that
the SparseCollection is not a refinement of the DenseCollection. The
basic reason for this is that the begin() member of the DenseCollection
would have to be mapped to either the nz_begin() or to the all_begin().
To which actually the user wants to map it to depends on the algorithm.
So for the sake of flexibility there is no inheritance relationship
between the DenseCollection and SparseCollection. Later we will see
however that adaptors allow to adapt a model of SparseCollection to be a
model of DenseCollection.

Next StructuredCollection is inherited from SparseCollection. The
StructuredCollection adds the ability (in respect to the
SparseCollection) to access the Structure seperatly.

And finally 1DCollection and 2DCollection also inherit from the
Collection concept. Basically these add an element-access operator that
take a number of indices that are equal to the dimension.

To clarify these concepts I also defined the Vector, DenseVector,
SparseVector and StructuredVector concepts in analogy with the
collections. The main difference is that containers *own* their elements
while collections do not mention element-lifetime at all (I focused on
vectors until now, matrices will come later).

Next I defined also the Structure and 1DStructure concept because it is
used by the StructuredCollection.

And of course to test these concepts, I also defined and implemented
some models as you can see here: These models currently only
implement the concepts mentioned above which makes that many important
features are not implemented yet. For instance, vectors always allocate
their elements on the heap (stack-based vectors are not implemented
yet), vectors can not be distributed (yet), etc. Also (numerical)
operations are not implemented yet. This will be done shortly and will
link the the mathematical concepts (as proposed by Peter) with the
concepts proposed here.

Of course the concepts and models are still a bit rough around the edges
but I wanted to verify the concepts and models as they are already with
all of you before starting to polish them further. Members that are
orange and red in the documentation are also not implemented yet because
  an optimal implementation is not very clear yet.

The test-directory ( also
contains a few tests that also serve as example for their respective
models. These can be compiled using bjam (Jamfile's are provided) or can
easily be compiled by adding the top-directory to the include-path (-I)

I have checked all the above modifications in on the 'tk1' branch. Next
I also copied this branch to the sourceforge site because this makes it
simpler to have a look at it as you can see here: