Boost logo

Ublas :

Subject: Re: [ublas] Slow (seeming) sparse matrix multiplication? (James Davidson)
From: Jörn Ungermann (j.ungermann_at_[hidden])
Date: 2010-01-30 07:30:13

Hello James,

we had the same problem. You might want to have a look at the
"axpy_prod" and "sparse_prod" functions, which offer specialized
implementations for sparse matrices. However, we found all sparse matrix
products severely lacking and finally implemented the sparse matrix
multiplications we needed ourselves (which are mostly several orders of
magnitude faster than the best ublas routine). Sadly, we could not spend
the effort to do a implementation general enough and worthy to be
included into ublas.

But if you need something along the lines of compressed_matrix *
compressed_matrix -> matrix, send me an email and I can send you our
code. We have not implemented all products with respect to combinations
of transposedness/row-column-majority, but the missing ones could be
easily added given the existing implementations. As the product of two
sparse matrices is seldom sparse itself (and certainly not in our
use-case) we have not thought about a compressed_matrix as target, which
certainly requires a special order in which the resulting matrix is to

Kind regards,
Joern Ungermann

> Date: Wed, 27 Jan 2010 17:56:25 -0500
> From: James Davidson <james_at_[hidden]>
> To: ublas_at_[hidden]
> Subject: [ublas] Slow (seeming) sparse matrix multiplication?
> Message-ID:
> <d5199cf81001271456v3b9a1301g66948f887655a6b5_at_[hidden]>
> Content-Type: text/plain; charset="iso-8859-1"
> Howdy,
> I am attempting to multiply two 1000x1000 compressed_matrix<double> matrices
> and the computation time seems excessive. When I compile the code attached
> at the end of this message I get the results:
> > g++ -DNDEBUG -I"/home/james/local/include/boost-1_37" -O3
> test_sparse_mult.cpp -o test_sparse_mult
> > time ./test_sparse_mult
> real 0m10.609s
> user 0m10.381s
> sys 0m0.012s
> I also compiled the code without the NDEBUG flag and obtained:
> > g++ -I"/home/james/local/include/boost-1_37" -O3 test_sparse_mult.cpp -o
> test_sparse_mult
> > time ./test_sparse_mult
> real 0m10.004s
> user 0m9.373s
> sys 0m0.568s
> As a reference, I ran substantially similar code in Matlab and achieved many
> orders of magnitude improvement in running time--reducing the execution time
> to 0.000262 seconds.
> Does this seem correct? Is there something I am missing? Any help on this
> matter will be greatly appreciated. Thanks.
> --James

Jörn Ungermann
Institut für Chemie und Dynamik der Geosphäre: Stratosphäre
Forschungszentrum Jülich
Telefon: +49 2461 61-1840
Forschungszentrum Juelich GmbH
52425 Juelich
Sitz der Gesellschaft: Juelich
Eingetragen im Handelsregister des Amtsgerichts Dueren Nr. HR B 3498
Vorsitzende des Aufsichtsrats: MinDir'in Baerbel Brumme-Bothe
Geschaeftsfuehrung: Prof. Dr. Achim Bachem (Vorsitzender),
Dr. Ulrich Krafft (stellv. Vorsitzender), Prof. Dr.-Ing. Harald Bolt,
Prof. Dr. Sebastian M. Schmidt