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)