Sunday, 3 September 2017

4.2-5 CLRS

4.2-5[CLRS], States that:
V. Pan has discovered a way of multiplying $68 \times 68$ matrices using $132,464$ multiplications, a way of multiplying $70 \times 70$ matrices using $143,640$ multiplications, and a way of multiplying $72 \times 72$ matrices using $155,424$ multiplications. Which method yields the best asymptotic running time when used in a divide and conquer matrix multiplication algorithm ?  How does it compare to Strassen's algorithm?


ANSWER:
Here is my try over this question:
We are provided with three options:
  1.  Use $68 \times 68$ matrices in order to find the multiplications of larger matrices.
  2.  Use $70 \times 70$ matrices.
  3.  Use $72 \times 72$ matrices instead.
But which one to choose? How to compare?
Well, if we want to compare these three, we need a (bigger) matrix that can use all three of them. Consider the LCM of $68$,$70$ and $72$: $42840$. So, if we get to multiply two $42840 \times 42840$ matrices, then we can test all the three of the submatrices!

So, let's do that.

I'll start with a smaller example in order to clarify stuff. Let's consider a multiplication of two $9 \times 9$ matrices. If we divide a $9 \times 9$ matrix into 9 $3 \times 3$ matrix, then we'll do $3^3=27$ $3 \times 3$ matrix multiplications. And if we claim that each  $3 \times 3$ matrix multiplication takes $k$ multiplications, then we can multiply two $9 \times 9$ matrices in $27 \times k$ multiplications.

Here, the claims are given in the question. All we have to find is the total number of multiplications.

CASE-1:
We'll get a $630 \times 630 $ matrix, thus $630^{3} \times 132464 = 3.3122 \times 10^{13}$ multiplications.

CASE-2:

We'll get a $612 \times 612 $ matrix, thus $612^{3} \times 143640 = 3.2925 \times 10^{13}$ multiplications.

CASE-3:

We'll get a $595 \times 595 $ matrix, thus $595^{3} \times 155424 = 3.2739 \times 10^{13}$ multiplications.So eventually, the least number of multiplications are in the case-3, when we take $72 \times 72$ matrices in a divide and conquer matrix-multiplication algorithm.

Now, guess what? I'm wrong.
 REAL ANSWER: 

The thing I'm calculating considers only the multiplications, not the additions that are done.
Well, I'd seen this  blog-post upon this question.  I didn't really understand it.  But later, I found my mistake. In the question number 4.2-4 of the same blog, we can find a formula: $$T(n) = k\times T(n/3)+\Theta(n^2)$$

which, by case-1 of the master theorem gives the answer $O(n^{log_3k})$. In this case we also consider the additions.
So, this blog gives the second way as the answer, and that seems legit too, because the third case might have extra additions, (because it has a bigger tree) leading to extra running time. Therefore, IMHO a $70 \times 70$ matrix should be used for the divide and conquer matrix-multiplication.
 

No comments:

Post a Comment

1498C - Planar reflections

1498C - Planar reflections Problem We have a set of $n$ 2D planes. A particle comes from the left, and goes through all the planes. Initiall...