Matrix Multiplication using Divide and Conquer

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

C₁₁ = A₁₁ B₁₁ + A₁₂ B₂₁

C₁₂ = A₁₁ B₁₂ + A₁₂ B₂₂

C₂₁ = A₂₁ B₁₁ + A₂₂ B₂₁

C₂₂ = A₂₁ B₁₂ + A₂₂ B₂₂

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 x n
// C is the output matrix of size n x 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(n³)

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:

C₁₁ = S₁ + S₄ – S₅ + S₇

C₁₂ = S₃ + S₅ 

C₂₁ = S₂ + S₄

C₂₂ = S₁ + S₃ – S₂ + S₆

Where,

S₁ = (A₁₁ + A₂₂) * (B₁₁ + B₂₂)

S₂ = (A₂₁ + A₂₂) *  B₁₁

S₃ = A₁₁ * (B₁₂ – B₂₂)

S₄ = A₂₂ * (B₂₁ – B₁₁)

S₅ = (A₁₁ + A₁₂) * B₂₂

S₆ = (A₂₁ – A₁₁) * (B₁₁ + B₁₂)

S₇ = (A₁₂ – A₂₂) * (B₂₁ + B₂₂)

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

C₁₂ = S₃ + S₅ 

= A₁₁ * (B₁₂ – B₂₂) + (A₁₁ + A₁₂) * B₂₂

= A₁₁ * B₁₂ – A₁₁ * B₂₂ + A₁₁ * B₂₂ + A₁₂ * B₂₂

= A₁₁ * B₁₂ + A₁₂ * B₂₂                                                                                                                

This is same as C₁₂ derived using conventional approach. Similarly we can derive all C_ij for strassen’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 x 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) = 7².T(n/2²)

                         .

                         .

                         .

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

Let’s assume n = 2^k ⇒ k = log₂ n

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

= 7^k .T (1)

= 7^k 

= 7^log₂ n 

= n^log₂  7 

=  n^2.81  < n³

Thus, running time of Strassen’s matrix multiplication algorithm O(n^2.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,

S₁ = (A₁₁ + A₂₂) x (B₁₁ + B₂₂)

S₂ = (A₂₁ + A₂₂) x B₁₁

S₃ = A₁₁ x (B₁₂  – B₂₂)

S₄ = A₂₂ x (B₂₁ – B₁₁)

S₅ = (A₁₁ + A₁₂) x B₂₂

S₆ = (A₁₁ – A₁₁) x (B₁₁ + B₁₂)

S₇ = (A₁₂ – A₂₂) x (B₂₁ + B₂₂)

Some Popular Problems Solved using Divide and Conquer

• Linear Search
• Binary Search
• Convex Hull
• Max-Min Problem
• Larger Integer Multiplication
• Strassen’s Matrix Multiplication
• Finding Exponent Problem
• Merge Sort
• Quick Sort

---

Additional Reading: Intuitive explanation of the Strassen matrix multiplication