Boost logo

Ublas :

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

Am Freitag, 16. Februar 2007 00:21 schrieb
> 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

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