Matrix Multiplication

Internal

• Algorithms | Divide and Conquer

Overview

The obvious algorithm for matrix multiplication in case of two matrices M (mxn) and N (nxp) is m * n * p. For simplicity, we assume the matrices are square, with the number of rows and columns equal to n. In this case the obvious algorithm for multiplication is O(n³).

One may think that a divide and conquer recursive algorithm may help

TODO

• problem statement
• naïve recursive solution
• Strassen algorithm

Overview

The asymptotic complexity is Θ(n^lg7).

TODO CLRS page 75.