Textbook.

CS 3343/3341  Analysis of Algorithms  Fall 2012  Recitation 9  Strassen Etc.     Answers

Remaining Problems:

---

4. Text, Exercise 4.2-7 on page 83. [Show how to multiply the complex numbers a + bi and c + di using only three multiplications of real numbers. The algorithm should take a, b, c, and d as input and produce the real component ac - bd and the imaginary component ad + bc separately.] [Hint: This is the same as the trick in the method for multiplying integers faster ( Multiply in Θ(n^1.585) ). Consider the expression (a + b)*(c + d).] [Well, follow the hint: (a + b)*(c + d) = a*c + a*d + b*c + b*d. This sum includes the imaginary part, and the extra pieces in the product are just the two halves of the real part. So ...

   First: 3 multiplications:
   
   m1 = a*c
   m2 = b*d
   m3 = (a + b)*(c + d)
   
   Then: real part = m1 - m2
   and   imag part = m3 - m1 - m2

   ]

   ---

5. Suppose one tried to mimic Strassen's approach to 2-by-2 and looked for a clever way to multiply 3-by-3 matrices, using fewer than 27 individual multiplications. We might work very hard and find a way to do this in, say, 23 multiplications, only to find that the work was useless, because the asymptotic bound in this case was worse that Strassen's bound for the 2-by-2 case. What is the biggest integer k that has the property that if we can multiply 3-by-3s in k multiplications, we would have a better bound than Strassen? [In other words, how far would we have to push the number down? What's the biggest k that would still improve on Strassen?] You should solve this problem by writing a recurrence for 3-by-3 matrices involving the variable k. Use the Master Theorem to solve this recurrence. [Recurrence: T(n) = k T(n / 3) + Θ(n²)
   Here a = k, b = 3, so the magic number is log₃(k), which we want to be less than log₂(7).

   log3(k) < log2(7) = 2.80735
   3log3(k) < 32.80735
   k < 21.84986, so k = 21, largest value that works.
   
   Or using only logs base e:
   loge(k) / loge(3) < loge(7) / loge(2)
   loge(k) < loge(7) * loge(3) / loge(2)
   loge(k) <  (1.94591 * 1.09861) / .69315 = 3.08419
   k < e3.08419 = 21.8498, so k = 21, largest value that works.
   
   Performance would be Big-Θ of log3(21) = loge(21) / loge(3) = 2.77124
    ..., but it is known that there is no way to multiply
   3-by-3 matrices in 21 scalar mults.
   

   ]

   ---

6. According to your text, V. Pan discovered a way of multiplying 68-by-68 matrices in 132464 scalar multiplications. Consider a divide-and-conquer strategy for multiplying matrices based on this discovery. Give the recurrence equation for such a divide-and-conquer algorithm. Give an expression for the Θ performance of this algorithm. (You don't need to use a calculator to work out the value of this expression.) [Hint: Don't let the big numbers intimidate you -- they're just numbers.] [Recurrence is T(n) = 132464 T(n / 68) + Θ(n²)
   Here a = 132464, b = 68, so the magic number is log₆₈(132464) = log_e(132464) / log_e(68) = 11.794066 / 4.2195077 = 2.795128, which gives a bound better than Strassen's.

   Notice that we would divide up 68²-by-68² = 4624-by-4624 matrices at the second stage, on to 68³-by-68³ = 314432-by-314432 at the third, and so on for higher powers of 68. Obviously this result is only of theoretical interest.]