Divide and Conquer Set 5 (Strassen’s Matrix Multiplication). Given two square matrices A and B of size n x n each, find their multiplication matrix. Following is a simple way to multiply two matrices. Time Complexity of above method is O(N 3 ). Divide and Conquer. Following is simple Divide and Conquer method to multiply two square matrices. 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 and cf + dh. In the above method, we do 8 multiplications for matrices of size N/2 x N/2 and 4 additions.

Explains how to multiply a matrix by a scalar and by another matrix. Demonstrates a useful technique for keeping track of matrix multiplication. Intuitively, I can see that it's true. However, when I try to formally prove it, I quickly get lost in the indices. What tricks can I use to keep things. Walkthrough: Matrix Multiplication The product of multiplying A by B is the following 3-by-3 matrix. 4-by-4 matrix partitioned into 2-by-2 sub -matrices.

Addition of two matrices takes O(N 2 ) time. So the time complexity can be written as. Simple Divide and Conquer also leads to O(N 3 ), can there be a better way. 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 x N/2 as shown in the above diagram, but in Strassen’s method, the four sub-matrices of result are calculated using following formulae. Time Complexity of Strassen’s Method.

In addition to the usual method of multiplying two matrices there is another method of matrix multiplication that gives the same result. It involves partitioning the. Note that the usual rules of matrix multiplication hold even when the block matrices are not square (assuming that the block sizes correspond). Of course, matrix.

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

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 ). Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.