Re: questions on ublas ?

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