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