Boost logo

Ublas :

Subject: Re: [ublas] [uBLAS] What's inside the uBLAS matrix multiplication algorithm?
From: Gunter Winkler (guwi17_at_[hidden])
Date: 2010-06-11 11:44:02

Hello Anders,

Anders Kabell Kristensen schrieb:
> I suppose the uBLAS algorithm is very complex and varies between
> methods such as Strassen's and even the naive approach when
> appropriate, right? Can anyone give an outline?
No, uBLAS uses very simple and straight-forward ways to compute matrix
products. The main concern of uBLAS was to give a reliable baseline for
linear algebra. Additionally to the basic prod() method there are some
specialized methods "axpy_prod" to provide faster implementations of y
-> y + Ax. However there are a lot of more sophisticated libraries
available via the "bindings".

> Would it be possible to make a realistic estimate on the complexity? I
> guess that would be an estimate about the performance on square matrices.
It is O(n^2) for full dense matrices. It is O(nnz) for sparse matrices
and it is O(n*k) for band matrices. You can check matrix_expression.hpp
for the class matrix_:matrix_product (or similar name) and
operations.hpp for axpy_prod().

Feel free to contribute more special products like block_prod, opb_prod
and axpy_prod.


__________ Hinweis von ESET NOD32 Antivirus, Signaturdatenbank-Version 5190 (20100611) __________

E-Mail wurde geprüft mit ESET NOD32 Antivirus.