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 = (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.

Happy hacking!

Advertisements

One response to “The Strassen Algorithm in C++

  • Russell L. Carter

    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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: