Quite some time ago I wrote about some experiments I did with some matrix multiplication algorithms. I’ve finally got around to cleaning up and posting (most of) the source code I used to generate the data in that post.

The source is now hosted in my GitHub repository here.

In the project is a few toys for playing around with matrices, but the meat is in

src/strassen/strassen_matrix_multiplier.hpp
src/strassen/parallel_strassen_matrix_multiplier.hpp

There’s a few other algorithms in there for comparison’s sake, as well as a simple testing client that provides some timing information. I’m using CMake to generate the Makefiles; if you’ve never used it before, you should. It’s great.

Some things to note:

- The Strassen algorithm has a very high constant factor; for this reason, for smaller matrices or sub-matrices, the code falls back to an optimized naive multiplication algorithm
- The algorithm needs to pad matrices with zeroes if they’re either non-square and/or have dimensions which are not a power of two. For this reason, if your input matrices have a square dimension something like N = (2
^{n }+ 1), the algorithm works with a matrix almost twice that size. For that reason it will perform badly on matrices with this characteristic.
- This implementation is mostly a demonstrative toy in the hope someone finds it useful; its not particularly optimized and the parallel Strassen class is kind of naive.

Happy hacking!

### Like this:

Like Loading...

*Related*

April 11th, 2011 at 23:20

I would be the last person to discourage people from rolling their own basic algorithms, on the principle that unless you’ve actually implemented even a naive version you don’t really understand what’s going on. However, if’n it were me and the performance mattered to the point of reaching for Strassen, I’d spend a little quality time with math-atlas first.

math-atlas.sourceforge.net

Packages available for myriad systems, including 64 bit SSE. However I always build mine from source optimized to my main dev box’s hardware config.

I only write this comment because I am very impressed with the high level of the analytic and literary components of the writing on your blog.