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
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 = (2n + 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.