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

From: Gunter Winkler (guwi17_at_[hidden])
Date: 2007-02-14 17:12:04

Am Mittwoch, 14. Februar 2007 22:17 schrieb 
Richard_Harding_at_[hidden]:
> > I believe CXSparse doesn't do reordering, so you'll have problems
> > with fill-in.
> > I think UMFPACK is a better choice, or use something like METIS to
> > do the reordering for you.
>
> My matrix A is not square which is also a requirement of UMFPACK. I
> whipped up a custom A'A function based on a column-major, gvov of
> compressed_vector that attempts to take advantage of the sparsity of
> the compressed_vector columns and the symmetric nature of the result.
> On a matrix A of dimension 60600x30302 with 241192 non-zero elements,
> the A'A operation took roughly 26 seconds. That's not as awful as I
> thought it would be....but still very expensive.

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) )

However, I don't know which way the computation prod(trans(A), A) 
chooses. 

BTW you can even call

axpy_prod(A, x, y, row_major_tag());
with A being compressed_matrix<T, column_major, ...> which in this case 
computes y += A'x

mfg
Gunter