Re: [ublas] Worst case time complexity of ublas::compressed_matrix operations?

From: Gunter Winkler (guwi17_at_[hidden])
Date: 2007-01-23 18:11:36

Paul C. Leopardi schrieb:
> After Pass 1, we know the total length of the new A. I assume tha between Pass 
> 1 and Pass 2 we have reallocated the space for A. Most likely this means that 
> we have created a new A of the right size and have either: 
> i. kept the old A; or 
> ii. copied the elements from the old A to the same places in the new A and 
> deleted the old A.
>
>   
Hm. When we have to reallocate and copy the elements of A then we should 
use the temporary. (However the reallocation is amortized constant time 
and should therefore not count)
>> >From what you have said about Pass 2, I assume that you mean to do ii above.
>>     
> In Pass 2, we scan the elements of old A and X backwards and insert the 
> appropriate result in the correct place in new A. The "correct place" is 
> always one position less than the previous insertion. We scan backwards so 
> that if old A is stored in the low positions of new A as per ii above, we do 
> not overwrite any values of old A which we have not yet scanned.
> For compressed_matrix, this algorithm should work.
>   

For coordinate matrix we just append the new values and call sort(). 
(Which sorts & accumulates duplicates)
Did you use append_element for the computation of the COO-sum ? I am not 
sure if the usual += dispatches to the right algorithm.

> I have repeated my test for mapped_marix and coordinate_matrix as well. 
> Results follow. They indicate that addition of coordinate_matrix is even 
> slower than compressed_matrix. I suppose your new algorithm could also be 
> used for coordinate_matrix?
The times are very long :-(

can you also try

#include <boost/numeric/ublas/vector_of_vector.hpp>

generalized_vector_of_vector< double, row_major, vector< X > >

with X = compressed_vector<double>, coordinate_vector<double>, 
mapped_vector<double>

mfg
Gunter