Strassen's Matrix Multiplication

Enhance Efficiency with Strassen's Matrix Multiplication

PRESENTATION

How Matrix Multiplication Works

Matrix Multiplication : Three ways to solve Matrix multiplication

1. Naive Method 2. Divide and Conquer Method 3. Strassen's Matrix Multiplication

01

Naive Method

For Matrix Multiplication

Naive Method

Here i iterates over the rows of the first matrix . j iterates over the columns of the second matrix. k variable is used to iterate over all the elements of the ith row and jth column because the coressponding elements of the ith row and jth columns need to be multiplied and added to be stored in the C [i][j]. Since this method uses 3 loops TIME COMPLEXITY OF THIS METHOD : O(N^3)

Naive Method: Following is a simple way to multiply two matrices. static int multiply(int A[][N], int B[][N], int C[][N]) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { C[i][j] = 0; for (int k = 0; k < N; k++) { C[i][j] += A[i][k]*B[k][j]; } } } }

+ info

02

Divide and Conquer Method

For Matrix Multiplication

Divide and Conquer Method

1. Divide matrices A and B in 4 sub-matrices of size N/2 x N/2 as shown in the below diagram.2. Calculate following values recursively.ae + bg, af + bh, ce + dg cf + dh. In Divide and conquer method total 8 recursive calls are made for matrix multiplications

TIME COMPLEXITY(DIVIDE AND CONQUER)

03

Strassen's Method

For Matrix Multiplication

Strassen's Matrix Multiplication

In the 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 simple divide and conquer method in the sense that this method also divide matrices to sub-matrices of size N/2 x N/2 as shown in the diagram, but in Strassen’s method, the four sub-matrices of result are calculated using following formulae.

Example

Strassen's Matrix Complexity Analysis

This algorithm reduces the number of required multiplications from 8 to 7, resulting in a slightly faster multiplication process for large matrices.T(N) = 7T(N/2) + O(N2) The time complexity of Strassen's algorithm for matrix multiplication is O(n^log2(7)), where n represents the size of the matrices being multiplied. From Master's Theorem, time complexity of above method is O(NLog7) which is approximately O(N^2.8074)

Strassen's Matrix Multiplication Complexity Comparisions

1. Time complexity Naive method : O(n^3) 2. Time complexity of Simple Divide and Conquer : O(n^3) 3. Time complexity of Strassen's Method : approx O(n^2.83)

Strassen's Matrix Multiplication Advantages

1. Faster computation: Strassen's algorithm can multiply matrices more quickly than the traditional method, especially for large matrices. 2. Reduced memory usage: Strassen's algorithm requires less memory compared to the traditional method, making it more efficient for memory- constrained environments. 3. Scalability: Strassen's algorithm's performance advantage becomes more pronounced as matrix size increases, making it suitable for large matrix computations.

Strassen's Matrix Multiplication Limitations

1. Strassen's Multiplication Method only works for square matrices , n is specifically power of 2.2. It's better to use the naive method for smaller matrices. 3. It only works for square matrices 4. Strassen's algorithm requires additional memory to store intermediate matrices during the recursive calls. This can be a limiting factor when dealing with very large matrices, as it may exceed the available memory capacity. 5. The Coppersmith-Winograd algorithm has a time complexity of O(n^2.376), which is an improvement over Strassen's algorithm.

Thanks!