A Review on Matrix Multiplication
Given two 2 nxn matrices X, Y and their product matrix Z,
X.Y = Z
we know that Zij = (ith row of X) . (jth column of Y). So, we take row from X, and column from Y.
zij = ∑xik . ykj where k is 1 < k < n.
For eg. : Let
X = a b and Y = e f
c d g h
|a b | | e f | | ae+bg af+bh |
| | X | | = | |
|c d | |g h | | ce+dg cf+dh |
So, with the input size of n2, and traversing the loop, one for each matrix and 1 for iteration on k, we have 3 loops. This naive algorithm requires three for loops, two to traverse the Z matrix and one to obtain the values from X and Y for the dot product. This has an overall runtime of O(n3).
If we think back to MergeSort, we can attempt to apply the Divide and Conquer algorithm design paradigm. We can split each matrix into 4 quadrants, as such:
Then, it can be proved that if we split the product matrix in 4 matrices as well, each submatrix will be the product of the corresponding submatrices in the two matrices.
Recursive algorithm #1Step 1 - Recursively compute the 8 necessary products
Step 2 _ do the necessary addtitions
Then to compute this product, we will need to do 8 recursive calls: 4 submatrices with two factors each. It turns out that this is no better than the naive approach. It also has a runtime of O(n3) using master method.
So, here it is same as iterative algorithm.
Strassen's algorithm (1969) - Recursive algorithm #2
Strassen's algorithm makes it possible to solve the problem with only 7 recursive calls. This may seem like a small decrease but if we do 1/8 less work on each time we recurse, the total amount of work saved is pretty significant. This turns out to have a subcubic runtime.
The Algorithm So what is the algorithm? We need 7 recursive calls to find 7 products:
Given two 2 nxn matrices X, Y and their product matrix Z,
X.Y = Z
we know that Zij = (ith row of X) . (jth column of Y). So, we take row from X, and column from Y.
zij = ∑xik . ykj where k is 1 < k < n.
For eg. : Let
X = a b and Y = e f
c d g h
|a b | | e f | | ae+bg af+bh |
| | X | | = | |
|c d | |g h | | ce+dg cf+dh |
So, with the input size of n2, and traversing the loop, one for each matrix and 1 for iteration on k, we have 3 loops. This naive algorithm requires three for loops, two to traverse the Z matrix and one to obtain the values from X and Y for the dot product. This has an overall runtime of O(n3).
If we think back to MergeSort, we can attempt to apply the Divide and Conquer algorithm design paradigm. We can split each matrix into 4 quadrants, as such:
|
| = |
|
Then, it can be proved that if we split the product matrix in 4 matrices as well, each submatrix will be the product of the corresponding submatrices in the two matrices.
Recursive algorithm #1Step 1 - Recursively compute the 8 necessary products
Step 2 _ do the necessary addtitions
Then to compute this product, we will need to do 8 recursive calls: 4 submatrices with two factors each. It turns out that this is no better than the naive approach. It also has a runtime of O(n3) using master method.
So, here it is same as iterative algorithm.
Strassen's algorithm (1969) - Recursive algorithm #2
Strassen's algorithm makes it possible to solve the problem with only 7 recursive calls. This may seem like a small decrease but if we do 1/8 less work on each time we recurse, the total amount of work saved is pretty significant. This turns out to have a subcubic runtime.
The Algorithm So what is the algorithm? We need 7 recursive calls to find 7 products:
P1 = A(F - H)
P2 = (A + B)H
P3 = (C + D)H
P4 = D(G - E)
P5 = (A + D)(E + H)
P6 = (B - D)(G + H)
P7 = (A - C)(E + F)
Then, it is claimed that
Step1 : Compute only 7 cleverly chosen products
Step 2 : Do the necessary, do the clever additions and subtractions.
This makes you wonder how in the world did Strassen come up with P1 through P7.
We have no idea. "How can we make this better?" This is the ultimate
question for coming up with better and better algorithms to solve our
problems.
Time complexity = O (n log 27 ) OR O (n2.8074) using master method.
Source
| = |
|
0 comments:
Post a Comment