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 could help, and the obvious divide and conquer algorithm would be to divide each matrix in equal blocks and perform recursive invocations multiplying the blocks:

     │ A B │       │ E F │
M =  │     │  N =  │     │   
     │ C D │       │ G H │

TODO

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

Overview

The asymptotic complexity is Θ(n^lg7).

TODO CLRS page 75.