From: jhrwalter (walter_at_[hidden])
Date: 2001-12-08 07:28:30
--- In boost_at_y..., Toon Knapen <toon.knapen_at_s...> wrote:
> jhrwalter wrote:
[snip]
> > compressed_array has a range insert member. Doesn't it suffice?
>
> parially. The last instruction here is also a std::sort. So if I
want to
> sort the whole thing only once I have to do only 1 call to the
range
> insert to insert the whole structure. This is doable but I would
need to
> allocate first a vector in which I will build up the coordinates
of
> all non-zeroes. Next I'll do a range insert. During the copy, space
to
> store the coordinates is allocated twice (once in my vector, once
in the
> compressed_array).
Ok, I understand the problem. May be we'll have to analyze, if and
how it's possible to build a compressed_array with deferred sorting.
BTW aren't others working on array containers with a std::map like
interface already?
> In the compressed_array, you store the structure along with the
content
> of the matrix (because it's a C-array of std::pair< index, value
>).
> In my (very limited) matrix lib, I seperated both so that I could
first
> create the structure and then create a matrix with the given
structure.
> Whereas maybe the latter approach offers more flexibility, I guess
it
> limits cache performance. I don't know if you already looked at
cache
> behaviour or what inspired storing the std::pair's in the C-array.
No, we didn't analyze cache behaviour. The design simply fitted well
with the existing dense matrices.
[snip]
> > Sorry, you've lost me. Are you talking about extending/changing
> > existing sparse matrix formats or about new CRS and CCS formats
here?
> Sorry, my explanation was not very clear. The bottom line though is
>
> that a sparse matrix need to build up in several steps :
>
>
> First I need to gather all the indices where a non-zero will be
stored.
> While building up this list, I will not sort the entries, just
push_back
> them in some vector.
Ok. Something like a vector<std::pair<std::size_t, std::size_t> >, if
I've understood it correctly?
> In a second step, I will sort all entries and format them in some
> specific way (COO, CSC, ... )
Ok. Here one can compress that vector<std::pair<std::size_t,
std::size_t> > also?
> In a third step, I create a sparse matrix (with the structure as an
> argument for its constructor) which will allocate space to store
the
> non-zeros for the indices known in advance.
Ok.
> Again, here I seperate structure from the values contained by the
> matrix. Maybe it is not optimal to store the structure and values
> seperatly : in memory, the indices can be far from their
corresponding
> value which may destroy cache-performance.
But it should be possible to get the Fortran storage layout. So may
be one could try to specialize to external functions in this case
also.
Regards
Joerg