Re: [ublas] Slow (seeming) sparse matrix multiplication? (James Davidson)

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
filled.

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
Dipl.-Mathematiker
Institut für Chemie und Dynamik der Geosphäre: Stratosphäre
Forschungszentrum Jülich
Telefon: [phone]
------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------
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
------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------