Re: [boost] Re: questions on ublas ?

From: Toon Knapen (toon.knapen_at_[hidden])
Date: 2001-12-07 08:37:08

jhrwalter wrote:

>>Most important though is that we prefer 
>>to first construct the structure of the matrix and later fill in 
>>the values. The speedup by constructing the structure first exactly 
>>comes from that the internal array do not need to be sorted the whole 
>>time. 
> 
>>Where you sort the compressed_array now the whole time, I would 
>> like to delay this sorting. This way it's more efficient.
>>

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

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.

>  
> 
>>After having built up the structure, the matrix would also need a 
>>constructor that takes the structure as an argument (not only as a 
>>template argument).
>>An option would be to add some members to work in non-sorted mode. 
>> For 
>>instance a member function add_nnz(size_type, size_type) or just 
>>add_nnz(size_type) that would add the entry but not force that 
>> data_ 
>>would be sorted as a post-condition. When the structure is used to 
>>construct another structure (like CSC) or used within a matrix 
>>constructor, the sort would be triggered. This sort can also be 
>>triggered by any call to any of  the other member functions of the 
>>object but this might be inefficient.
>>
>  
> 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.

In a second step, I will sort all entries and format them in some 
specific way (COO, CSC, ... )

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.

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.