Matrix Multiplication

Internal

• Divide and Conquer Algorithms
• Karatsuba Multiplication

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. Note that while usually we use "n" to denote the input size, here we use "n" to denote the matrix dimension, so the input size in this case is O(n²). In this case the obvious algorithm for multiplication is O(n³). That matches the intuition as the straightforward iterative algorithm is a triple nested loop over 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 - none of the products re-occur, they are distinct), 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 Case 3 of 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 only 7 recursive calls.

Strassen's Algorithm for Matrix Multiplication

The Strassen algorithm recursively computes the products of smaller (n/2) matrices, but it'll only be 7 of them:

P₁=A(F-H), P₂=(A+B)H, P₃=(C+D)E, P₄=D(G-E), P₅=(A+D)(E+H), P₆=(B-D)(G+H), P₇=(A-C)(E+F).

In the combine phase, it'll combine the results of the recursive calls, using only addition and subtraction (O(n²)):

         │ AE+BG AF+BH │     │ P5+P4-P2+P6   P1+P2       │
M x N =  │             │  =  │                          │ 
         │ CE+DG CF+DH │     │ P3+P4         P1+P5-P3-P7 │      

This is the same type of optimization applied in the case of Karatsuba integer multiplication algorithm.

More details on Strassen multiplication in CLRS, page 75.

Strassen's Algorithm Time Complexity

Applying the Master Method for a = 7 (7 sub-problems), b = 2 (the size of the subproblem is half of the size of the initial problem) and the combine phase complexity is O(n²) so d = 2, a/b^d is bigger then 1, so according to the Case 3 of the master method, the asymptotic complexity is Θ(n^log₂7) = Θ(n^log7).

The key insight was to find a way to reduce the number of recursive calls, in the same way Karatsuba method of multiplying to n-size integers takes advantage of Gauss' trick to perform only 3 recursive calls instead of 4.