CSE 417 Assignment #3
Autumn 2002

Due: Friday, November 15, 2002.

Written portion:

1. Modify Karatsuba's algorithm based on splitting the polynomials into 3 pieces instead of two. Base your algorithm on an algorithm for multiplying two degree 2 polynomials that uses evaluation and interpolation. It is possible to do this degree 2 multiplication with as few as 5 multiplications of coefficients (but with other multiplications or divisions involving constants like the dividing by 2 we needed in the variant of Karatsuba's algorithm from class - see the on-line version of the slides since this wasn't in the version handed out).

   1. You may not be able to get an algorithm that does only 5 multiplications of coefficients on the first try. You will get full credit if you can do it with 6 multiplications of coefficients.

      1. What running time would your generalized algorithm use?

      2. Is this better or worse than Karatsuba's algorithm?

   2. (Bonus) Do the above based on an algorithm that uses only 5 multiplications.

2. In class we looked at a simple example of how a dynamic programming algorithm could compute the n^th Fibonacci number in O(n) addition steps. (This was a lot better than the natural recursive algorithm which took exponential time!) If we allow multiplication as well as addition we can write some matrix operations that let us compute the n^th Fibonacci number F(n) with even fewer operations using divide and conquer: We can write a matrix equation:

   F(k-1) F(k)

   =

   0 1 1 1

   .

   F(k-2) F(k-1)

   In particular, if we let A be the 2x2 matrix

   0 1 1 1

   then F(n) is the second component of A^n-1.[0 1]^T where [0 1]^T is just a column vector with first row 0 and second row 1 and A^n-1 is n-1 copies of matrix A multiplied together. Use this fact with divide and conquer to design an algorithm that uses only O(log n) multiplications and additions of integers to compute F(n).

Programming plus write-up portion

In describing and analyzing Strassen's algorithm we assumed that we used divide and conquer all the way down to tiny matrices. However, on small matrices the ordinary matrix multiplication algorithm will be faster because of lower overhead. This is a common issue with divide and conquer algorithms. The best way to run these algorithms is to test the input size n at the start to see if it is big enough to make using divide and conquer worthwhile; if n is larger than some threshold then the algorithm would do a level of recursion, if n is below that threshold then it would do the non-recursive algorithm. Your job is to figure out the best choice for that threshold value for a version of Strassen's algorithm based on your implementation. (See the class slides for the description of the recursion used in Strassen's algorithm and for the code for the basic non-recursive algorithm for matrix multiplication.) Steps:

1. First, write a program that implements the ordinary n³ algorithm for matrix multiplication over the integers (see the slides).

2. Next, write a recursive program that the implements a pure version of Strassen's algorithm for matrix multiplication over the integers (see the slides). To keep the recursion simple you can assume that the input matrices are nxn matrices where n that is a perfect power of 2.

3. Now modify your recursive program so that it uses an extra number s and tests the input size n of the matrices first. If n is at most s then it skips out of the recursion and calls the simple version from part a above.

4. Your job now is to figure out which value of s is best to use with your algorithm. To do so, you will need to figure out how long your code takes to work and you will need sample inputs of various sizes. Code for generating test matrices is available here. For information about how to time your code see Timing Instructions. Try out various values of s, which you can also assume is a power of 2 since we are only working with sizes n that are powers of 2.

• your code

• the timings that you found

• and the choice of s you found works best

(Bonus) Generalize your code so that it works with matrices of any dimension, not just powers of 2. Figure out the best value of s to use in this case.