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

From: Gunter Winkler (guwi17_at_[hidden])
Date: 2007-01-21 14:17:56

Paul C. Leopardi schrieb:
> Hi all,
> Is the worst case time complexity of ublas::compressed_matrix operations 
> documented anywhere? For addition of square matrices where each of the 
> operands is half full with no non-zeros in common, using operator+=
> >from Boost 1.33.0 and 1.33.1, I'm getting about O(dim^2) for ublas::matrix and 
> about O(nnz * dim^2) for ublas::compressed_matrix. Is this what should be 
> expected in this case? Is it the worst case? 
>   
The worst case for a compressed matrix is to insert elements from last 
(n,m) to first (0,0) because you essentiallialy insert a new element 
into an array. This means (1) realloc if necessary (in armotized 
constant time) (2) shift all elements one position forward (in linear 
time O(nnz)) (3) insert the new data at position 0. For this operation 
you should use a different storage scheme:

coordinate_matrix: += means appending elements to an array (you need 
more memory later need a sort/compress operation in O(nnz (1 + log(nnz)))).

generalized_vector_of_vector with compressed vectors: element lookup is 
O(log(nnz per row)) and worst case insert is O(nnz per row), average 
should be O(log(nnz per row))

generalized_vector_of_vector with coordinate vectors: += (aka 
v.append_element(k,x) ) is O(1) + final sort.

I use the second one for my finite element assembly.

btw:  the construction of a compressed_matrix from a coordinate matrix 
is a O(nnz) operation. This could even be done inplace (but this is not 
implemented, because I have no idea how to do this without too much ugly 
tricks.). Please have a look at the constructors of compressed_matrix. 
(I even have a near optimal implementation of 
compressed_matrix.assign_temporary(coordinate_matrix) in my files.)

mfg
Gunter