Re: [boost] Re: questions on ublas ?

From: Toon Knapen (toon.knapen_at_[hidden])
Date: 2001-12-08 09:41:10

jhrwalter wrote:

> --- 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?

who are you thinking of ?

>>>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?

Indeed.

>  
> 
>>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.

Well, CSC is defined by using 3 different arrays (Fortran can't handle 
sotring pairs in a vector ;-) and since it's known to be performant, it 
would not be too bad for cache performance.
But indeed, the storage class can indeed choose both strategies. I might 
implementing a CSC storage a try next week.

(sorry for the lazy indentation, I really need to replace this lousy 
mozilla with a decent mail client)