Algorithms StudyNote-3: Divide and Conquer — Strassen’s Matrix Multiplication

Brute Force

Given two square matrices A and B of size n x n each, the straightforward iterative way to find their multiplication matrix C is by multiplying each row of A by each column of B.

def multiply(A, B, n):
    C = []
    for i in range(n):
        for j in range(n):
            for k in range(n):
                C[i][j] += A[i][k]*B[k][j]
    return C 

We can easily see the 3 for loops and draw the conclusion that the time complexity is θ(n³).

Simple Divide and Conquer

We want to apply divide and conquer to the problem for better solution. The idea is that we divide matrices A and B in 4 sub-matrices of size n/2 × n/2. Then recursively compute the 8 necessary products, and do the additions ae + bg, af + bh, ce + dg and cf + dh, which is θ(n²) time.

The total time can be written as

T(N) = 8T(N/2) + O(N²)

Follows from the Master’s Theorem, it leads to the fact that the total runtime is θ(n³) , which is not an improvement from the brute force approach.

Strassen’s Algorithm (1969)

In the above divide and conquer method, the main component for high time complexity is 8 recursive calls. The idea of Strassen’s method is to reduce the number of recursive calls to 7. Strassen’s method is similar to above simple divide and conquer method in the sense that this method also divide matrices to sub-matrices of size N/2 × N/2 as shown in the above diagram, but in Strassen’s method, the four sub-matrices of result are calculated using following formulae.

Addition and Subtraction of two matrices takes O(N²) time. So time complexity can be written as

T(N) = 7T(N/2) + O(N²)

From Master's Theorem, time complexity of above method is approximately O(N^log7), which is better than cubic time. However, generally Strassen’s Method is not preferred for practical applications for following reasons:

1. The constants used in Strassen’s method are high and for a typical application Naive method works better.
2. For Sparse matrices, there are better methods especially designed for them.
3. The submatrices in recursion take extra space.
4. Because of the limited precision of computer arithmetic on noninteger values, larger errors accumulate in Strassen’s algorithm than in Naive Method (Source: CLRS Book)

Code

Reference

Divide and Conquer | Set 5 (Strassen's Matrix Multiplication) - GeeksforGeeks

Strassen's Subcubic Matrix Multiplication Algorithm - Week 2 | Coursera