Subject: Re: [ublas] [uBLAS] What's inside the uBLAS matrix multiplication algorithm?
From: Benjamin Sobotta (benjamin.sobotta_at_[hidden])
Date: 2010-06-10 08:26:06
> Hi there, this is my first post. Thank you for your time.
> I'm implementing an algorithm where fast matrix multiplication is
> essential and the theoretical running-time is closely connected to the
> running-time of the matrix multiplication algorithm being used. As a
> matter of fact, some choices within the algorithm are made on the basis
> of the time complexity of matrix multiplication. Therefore, I'm
> interested in knowing exactly what's inside the uBLAS matrix
> multiplication algorithm. For example, naive mat.mult. has a complexity
> of O(n^3), whereas Strassen's method
> (http://en.wikipedia.org/wiki/Strassen_algorithm) has a complexity of
> 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?
> 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.
> And a related question: is it possible to force uBLAS to use naive
> mattrix multiplication? I need to use the naive approach, but if I
> implement it myself, I guess I wont be competitive with uBLAS.
> Thanks again,
> Anders K
In short, if matrix multiplication performance is critical, you do *not* want
to go with uBLAS.
I your case I recommend using uBLAS only to handle matrices and employ
specifically crafted high performance libraries such as ATLAS
(http://math-atlas.sourceforge.net/) for computation.
There are actually bindings available for use with such third party libraries
in the sandbox.