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

From: Gunter Winkler (guwi17_at_[hidden])
Date: 2007-02-16 03:17:00

Am Freitag, 16. Februar 2007 00:21 schrieb 
Richard_Harding_at_[hidden]:
> Does this make sense or is there a more efficient way to do this?

The inner_prod is efficient (and actually the ublas::inner_prod for 
sparse vectors does exactly the same).

However you loop over the whole (upper?) triangle of A'A. Thus your best 
complexity is O(n^2 * (nnz per row)). The best theoretical complexity 
is something like O(nnz^2) (note that it should be independent of the 
size of the matrix). This can only be achieved by precomputing the 
sparsity pattern of the result.

BTW: If you really look for optimal performace, have a look at CXSparse 
from
http://www.cise.ufl.edu/research/sparse/CXSparse/

This library provides optimal algorithms for transpose, multiply, 
preorder, qr and more with an easy usable C-Interface. (all for CCS 
matrices)

mfg
Gunter