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

From: Gunter Winkler (guwi17_at_[hidden])
Date: 2007-02-15 15:25:34

Am Donnerstag, 15. Februar 2007 20:19 schrieb 
Richard_Harding_at_[hidden]:
> > Did you try to multiply a column major A' with a row major A? Then
> > you can compute the columns of A'A one by one - each as a linear
> > combination of a few columns of A'. (call axpy_prod(AT,x,y,false)
> > with AT=a column major copy of A', x = row(A, i) )
>
> I'm confused! A is mxn and A' is nxm. Multiplying A' by a row in A
> has a mismatch in dimension: (nxm) * (nx1).

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)

mfg
Gunter