4.2-6[clrs]:
Case-1:
We want to multiply a $kn \times n$ matrix with a $n \times kn$ matrix. Now we can see that the $kn \times n$ matrix is composed of $k$, $n \times n$ matrices. We can say the same thing for the $n \times kn$ matrix.
Therefore we can rewrite both the matrices as $k \times 1$ and $1 \times k$, by assuming each $n \times n$ matrix as a single element.
Now, if we want to multiply a $k \times 1$ matrix by a $1 \times k$ matrix, then we'll do $k^2$ multiplications, along with no additions. So if $T(kn \times n,n \times k)$ represents the running times of the multiplication of these two matrices then:$$T(kn \times n,n \times kn) = k^2 T(n \times n,n \times n)+ O(1)$$
And, by Strassen's Algorithm, we know that $T(n \times n,n \times n)= n^{log_2 7}$. Therefore, $$T(kn \times n, n \times kn)=k^2 \times n^{log_2 7}$$
Case-2:
Now, in this case, we want to multiply a $n \times kn$ matrix by a $kn \times n$ matrix. Now again, we'll change them into $ 1 \times k$ into $k \times 1$ matrices. Notice that this multiplication requires $k$ multiplications of $n \times n$ matrices and $k-1$ additions. Therefore, $$T(n \times kn, kn \times n)= k T(n \times n) +O(k)$$
Which, equals:
$$T(n \times kn,kn \times n) = k \times n^{log_2 7}+O(k) = k \times n^{log_2 7}$$
How quickly can you multiply a $kn \times n$ matrix by an $n \times kn$ matrix, using Strassen's algorithm as a subroutine? Answer the same question with the order of the input matrices reversed.Well, this one was easy. I don't know why I couldn't do it earlier. So,
Case-1:
We want to multiply a $kn \times n$ matrix with a $n \times kn$ matrix. Now we can see that the $kn \times n$ matrix is composed of $k$, $n \times n$ matrices. We can say the same thing for the $n \times kn$ matrix.
Therefore we can rewrite both the matrices as $k \times 1$ and $1 \times k$, by assuming each $n \times n$ matrix as a single element.
Now, if we want to multiply a $k \times 1$ matrix by a $1 \times k$ matrix, then we'll do $k^2$ multiplications, along with no additions. So if $T(kn \times n,n \times k)$ represents the running times of the multiplication of these two matrices then:$$T(kn \times n,n \times kn) = k^2 T(n \times n,n \times n)+ O(1)$$
And, by Strassen's Algorithm, we know that $T(n \times n,n \times n)= n^{log_2 7}$. Therefore, $$T(kn \times n, n \times kn)=k^2 \times n^{log_2 7}$$
Case-2:
Now, in this case, we want to multiply a $n \times kn$ matrix by a $kn \times n$ matrix. Now again, we'll change them into $ 1 \times k$ into $k \times 1$ matrices. Notice that this multiplication requires $k$ multiplications of $n \times n$ matrices and $k-1$ additions. Therefore, $$T(n \times kn, kn \times n)= k T(n \times n) +O(k)$$
Which, equals:
$$T(n \times kn,kn \times n) = k \times n^{log_2 7}+O(k) = k \times n^{log_2 7}$$
No comments:
Post a Comment