Strassen’s Algorithm for Matrix Multiplication

Given two n by n matrices A and B, the “typical” way of computing their product C = A • B is given by:

Matrix Multiplication: Intuitive Method

Even though this may be the most intuitive way to determine the product between two matrices, it is definitely not the most efficient. As evident from the three nested for loops in the pseudocode above, the complexity of this algorithm is O(n^3).

Matrix Multiplication: Strassen’s Algorithm

Strassen’s algorithm, on the other hand, is asymptotically more efficient with a time complexity of about O(n^log7), which equates to about O(n^2.81) (We will see how this is derived shorty). It uses a divide-and-conquer approach along with a nice math trick to reduce the number of computations needed to calculate the product of two matrices. The algorithm works as follows:

Split A and B into four matrices each:

Then calculate the following ten matrices:

Using the derived matrices above, calculate the following seven matrices recursively:

Finally, although the algebra is omitted here, one can easily confirm that C = A • B can be constructed in the following way:

Thanks for reading! If you find an error in this post, please feel free to comment below and I will do my best to address any issues.