Matrix Multiplication

Internal

• Algorithms | Divide and Conquer

Overview

The straightforward iterative 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 │

In this case final result is obtained by multiplying the blocks as follows:

         │ AE+BG AF+BH │
M x N =  │             │  
         │ CE+DG CF+DH │

However, applying Mater Method to infer the time complexity of the recursive multiplication algorithm for a = 8 (we invoke recursively eight times: AE, BG, AF, BH, CE, DG, CF and DH), b = 2 (we multiply matrices twice as small, each matrix of size n/2 * n/2) and the combine step complexity is O(n²) so d = 2. a/b^d is 8/2² = 2, so according to the Master Method, the complexity is bounded by O(n^log_ba) = O(n³), the same as the straightforward iterative method.

An improvement to this upper bound is provided by the Strassen method, which cleverly proposes just 7 recursive calls.

Strassen's Algorithm for Matrix Multiplication

The asymptotic complexity is Θ(n^log7).

TODO CLRS page 75.