The Strassen Algorithm in C++

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ⁿ + 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!

Advertisement