Strassen Matrix Multiplication

Matrix multiplication algorithm. The simple and obvious implementation is $O(n^3)$. Strassen improves on this by eliminating a recursive call.

Although this is more efficient in terms of algorithmic complexity, it’s actually less performant for anything expect extremely large matrices because of the high number of constant operations.

TODO: THIS IS WRONG, REWRITE THIS PARAGRAPH Using C, the largest matrix that can be multiplied using the recursive Strassen algorithm without a stack overflow is 256 X 256. Strassen runs slower than the standard brute force implementation for all practical test cases. Therefore the utility of this algorithm isn’t immediately obvious. Further tests using either a loop or tail call optimized language are required.

TODO: Create head-to-head comparison between Strassen and naive matrix multiplication

Click here for a refresher on matrix multiplication.

History

For many years, it was assumed that $O(n^3)$ was the best possible runtime for matrix multiplication. There were even some proofs to that effect. However, in 1969 Volker Strassen discovered the now famous Strassen Matrix Multiplication algorithm.

Asymptotic Complexity

$O(n^{2.81})$

Pseudo Code

Assumptions

  • matrices are square
  • size of matrices is a power of 2
n = size of matrices
A = matrix 1
B = matrix 2

if n == 1
    return A X B

split matrices in quadrants and recursively multiply

    a | b       e | f
A = -----   B = -----
    c | d       g | h

p1 = a(f-h)
p2 = (a+b)h
p3 = (c+d)e
p4 = d(g-e)
p5 = (a+d)(e+h)
p6 = (b-d)(g+h)
p7 = (a-c)(e+f)

        p5+p4-p2+p6 | p1+p2
return  --------------------------
        p3+p4       | p1+p5-p3-p7

Source Code

Full Repo

Relevant Files:

Click here for build and run instructions