Re: [ublas] Computing sparse A'A.........

From: Richard_Harding_at_[hidden]
Date: 2007-02-15 18:21:58

> Sorry, but I was confused ;-) Of course you have to multiply A' by the
> first _column_ of A. Thus the product of two column major sparse
> matrices can be computed quite efficiently. The only problem is, that
> ublas currently has no optimized linear combination of sparse vectors.

> However you can choose whether you prefer
> (1) compressed_vector += alpha * compressed_vector
> (2) coordinate_vector += alpha * (any sparse vector)

> (1) is the topic of another thread (worst case time complexity)
> (2) can be fast by using append_element() and a final sort()

> (3) do it like suggested in the literature:

> scatter(sparse_1, dense)
> dense += sparse_2
> ...
> dense += sparse_n
> gather result from dense (<- this is the tricky part)

How about something like the attached file? I've implemented a
compressed_vector inner-product based on the sparsity of the two vectors
(i.e. only multiplying when both vectors have a non-zero in the same
position). That routine is used by another one that performs the A'A
between two generalized_vector_of_vector (that stores compressed_vector).
Notice that you do not actually need A' to perform A'A. Although A should
be column-major for best performance.

Does this make sense or is there a more efficient way to do this?

Thanks!

(See attached file: sparse_inner_prod.h)