|
|
Ublas : |
Subject: Re: [ublas] Efficiency of product of two sparse matrices
From: Ungermann, Jörn (j.ungermann_at_[hidden])
Date: 2012-12-06 04:47:20
Hi George,
this is not a good storage layout for the matrix product.
There are two major costs involved:
1) finding the right entries in A^T and A to multiply with one another.
2) writing the stuff into the target matrix. If this cannot be done
consecutively, performance will seriously suffer from copy operations.
My first tip would be to use a coordinate_matrix as result matrix and only
copy the result to a compressed matrix after the product is done.
Secondly, copying the transpose matrix into a column_major matrix might
help, too, but this depends more on the employed algorithm, and I forgot,
which kernel is used by sparse_prod.
If these tips are not sufficient or you cannot spend the additional memory,
you might want to search the mailing list for a patch proposal of mine that
offers a series of different product kernels suited for a wide range of
matrix types. All of these are at least as efficient as the ublas kernels
and some improve the performance dramatically. The mail contains a list of
measurements for products involving various types.
Either way, you might think about just not doing the matrix product. If you
can avoid it (and one mostly can), this would be the best solution.
If you have further questions, you may contact me.
Cheers,
Jörn
> -----Original Message-----
> From: ublas-bounces_at_[hidden] [mailto:ublas-
> bounces_at_[hidden]] On Behalf Of George Slavov
> Sent: Dienstag, 4. Dezember 2012 22:03
> To: ublas_at_[hidden]
> Subject: [ublas] Efficiency of product of two sparse matrices
>
> In my project I need to form the product A^T A where A is a
> compressed_matrix, but it's proving to be a big bottleneck in my code,
> taking on the order of 10 seconds. The result is also very sparse. The
> matrix has a size of about 13000x13000 and has about 37000 nonzero
> entries. The product of sparse matrices is generally not sparse, but my
> matrix is structured enough that the product has roughly the same
> sparsity as A.
>
> The code I'm using is basically.
>
> typedef ublas::compressed_matrix<T, ublas::column_major, 0,
> ublas::unbounded_array<unsigned int>, ublas::unbounded_array<T> >
> sparse_matrix;
>
> sparse_matrix A(13000, 13000)
> sparse_matrix result(13000, 13000)
> // fill A
> sparse_prod(trans(A), A, result, false)
>
>
> Are there any conditions on the use of sparse_prod which I'm not aware
> of with regard to matrix orientations? My A is column major so the
> transpose is row_major. I would have thought that would be the optimal
> storage to form the product since sums range over rows of A^T and
> columns of A.
>
> Regards,
> George
> _______________________________________________
> ublas mailing list
> ublas_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/ublas
> Sent to: j.ungermann_at_[hidden]