In this article, we will review Matrix Multiplication using Divide and Conquer along with the conventional method. We will also compare the performance of both methods.

Conventional Approach

Matrix multiplication is an important operation in many mathematical and image processing applications. Suppose we want to multiply two matrices A and B, each of size n x n,  multiplication is operation is defined as

C11      = A11 B11 + A12 B21

C12    =   A11 B12 + A12 B22

C21    =   A21 B11 + A22 B21

C22    =   A21 B12 + A22 B22

This approach is very costly as it required 8 multiplications and 4 additions.

Algorithm

Algorithm MATRIX_MULTIPLICATION(A, B, C)
// A and B are input matrices of size n  n
// C is the output matrix of size n  n

for i ← 1 to n do

	for j ← 1 to n do

		C[i][j] ← 0	
		for k ← 1 to n do

			C[i][j] ← C[i][j] + A[i][k]*B[k][j]
		end

	end

end

Complexity Analysis

The innermost statement is enclosed within three for loops. That statement runs in constant time, i.e. in O(1) time. Running time of algorithm would be,

Running time of this algorithm is cubic, i.e. O(n3)

Matrix Multiplication using Strassen’s Method

Strassen suggested a divide and conquer strategy-based matrix multiplication technique that requires fewer multiplications than the traditional method. The multiplication operation is defined as follows using Strassen’s method:

C11 = S1 + S4 – S5 + S7

C12 = S3 + S5 

C21 = S2 + S4

C22 = S1 + S3 – S2 + S6

Where,

S1 = (A11 + A22) * (B11 + B22)

S2    =   (A21 + A22) *  B11

S3    =   A11 * (B12 – B22)

S4    =   A22 * (B21 – B11)

S5      =   (A11 + A12) * B22

S6    =   (A21 – A11) * (B11 + B12)

S7    =   (A12 – A22) * (B21 + B22)

Let us check if it is same as the conventional approach.

C12    =   S3 + S= A11 * (B12 – B22) + (A11 + A12) * B22

=   A11  * B12 – A11 * B22 + A11 * B22 + A12 * B22

=   A11 * B12 + A12  * B22                                                                                                                

This is same as C12 derived using conventional approach. Similarly we can derive all Cij for stressen’s matrix multiplication.

Algorithm

Algorithm STRESSEN_MAT_MUL (int *A, int *B, int *C, int n)
// A and B are input matrices
// C is the output matrix
// All matrices are of size n  n

if n == 1 then
	*C = *C + (*A) * (*B)
else
	STRESSEN_MAT_MUL (A, B, C, n/4)
	STRESSEN_MAT_MUL (A, B + (n/4), C + (n/4), n/4)
	STRESSEN_MAT_MUL (A + 2 * (n/4), B, C + 2 * (n/4), n/4)
	STRESSEN_MAT_MUL (A + 2 * (n/4), B + (n/4), C + 3 * (n/4), n/4)
	STRESSEN_MAT_MUL (A + (n/4), B + 2 * (n/4), C, n/4)
	STRESSEN_MAT_MUL (A + (n/4), B + 3 * (n/4), C + (n/4), n/4)
	STRESSEN_MAT_MUL (A + 3 * (n/4), B + 2 * (n/4), C + 2 * (n/4), n/4)
	STRESSEN_MAT_MUL (A + 3 * (n/4), B + 3 * (n/4), C + 3 * (n/4), n/4)
end

Complexity Analysis of Matrix Multiplication using Divide and Conquer approach

The conventional approach performs eight multiplications to multiply two matrices of size 2 x 2. Whereas Strassen’s approach performs seven multiplications on the problem of size 1 x 1, which in turn finds the multiplication of 2 x 2 matrices using addition. In short, to solve the problem of size n, Strassen’s approach creates seven problems of size (n – 2). Recurrence equation for Strassen’s approach is given as,

T(n) = 7.T(n/2)

Two matrices of size 1 x 1 needs only one multiplication, so the base case would be, T (1) = 1. Let us find the solution using the iterative approach. By substituting n = (n / 2) in above equation,

T(n/2) = 7.T(n/4)

⇒ T(n) = 72.T(n/22)

                         .

                         .

                         .

T(n)    =   7k.T(2k)

Let’s assume n   =   2k ⇒ k = log2 n

T (n) = 7k .T(2k/2k)  

= 7k .T (1)

= 7

= 7log2 n 

= nlog2  7 

=  n2.81  < n3

Thus, running time of Strassen’s matrix multiplication algorithm O(n2.81), which is less than cubic order of traditional approach. The difference between running time becomes significant when n is large.

Example of Matrix Multiplication using Divide and Conquer Approach

Problem: Multiply given two matrices A and B using Strassen’s approach, where

Solution:

let,

S1 = (A11 + A22) x (B11 + B22)

Matrix Multiplication using Divide and Conquer

S2 = (A21 + A22) x B11

Matrix Multiplication using Divide and Conquer

S3 = A11 x (B12  – B22)

Matrix Multiplication using Divide and Conquer

S4 = A22 x (B21 – B11)

Matrix Multiplication using Strassen's method

S5 = (A11 + A12) x B22

Matrix Multiplication using Strassen's method

S6 = (A11 – A11) x (B11 + B12)

Matrix Multiplication using Strassen's method

S7 = (A12 – A22) x (B21 + B22)

Matrix Multiplication using Strassen's method
Matrix Multiplication using Strassen's method
Matrix Multiplication using divide and conquer

Additional Reading: Intuitive explanation of the Strassen matrix multiplication