Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
CS 124 Programming Assignment
Your name(s) (up to two):
Collaborators: (You shouldn’t have any collaborators but the up-to-two of you, but tell us if you
did.)
No. of late days used on previous psets:
No. of late days used after including this pset:
Homework is due Wednesday 2021-03-24 at 11:59pm ET. You are allowed up to twelve (college)/forty
(extension school) late days through the semester, but the number of late days you take on each assignment
must be a nonnegative integer at most two (college)/four (extension school).
Overview:
Strassen’s divide and conquer matrix multiplication algorithm for n by n matrices is asymptotically
faster than the conventional O(n3) algorithm. This means that for sufficiently large values of n, Strassen’s
algorithm will run faster than the conventional algorithm. For small values of n, however, the conventional
algorithm may be faster. Indeed, the textbook Algorithms in C (1990 edition) suggests that n would have
to be in the thousands before offering an improvement to standard multiplication, and “Thus the algorithm
is a thoeretical, not practical, contribution.” Here we test this armchair analysis.
Here is a key point, though (for any recursive algorithm!). Since Strassen’s algorithm is a recursive
algorithm, at some point in the recursion, once the matrices are small enough, we may want to switch
from recursively calling Strassen’s algorithm and just do a conventional matrix multiplication. That is,
the proper way to do Strassen’s algorithm is to not recurse all the way down to a “base case” of a 1 by 1
matrix, but to switch earlier and use conventional matrix multiplication. That is, there’s no reason to do
a “base case” of a 1 by 1 matrix; it might be faster to use a larger-sized base case, as conventional matrix
multiplication might be faster up to some reasonable size. Let us define the cross-over point between the
two algorithms to be the value of n for which we want to stop using Strassen’s algorithm and switch to
conventional matrix multiplication. The goal of this assignment is to implement the conventional algorithm
and Strassen’s algorithm and to determine their cross-over point, both analytically and experimentally.
One important factor our simple analysis will not take into account is memory management, which may
significantly affect the speed of your implementation.
Tasks:
1. Assume that the cost of any single arithmetic operation (adding, subtracting, multiplying, or dividing
two real numbers) is 1, and that all other operations are free. Consider the following variant of
Strassen’s algorithm: to multiply two n by n matrices, start using Strassen’s algorithm, but stop the
recursion at some size n0, and use the conventional algorithm below that point. You have to find a
suitable value for n0 – the cross-over point. Analytically determine the value of n0 that optimizes the
running time of this algorithm in this model. (That is, solve the appropriate equations, somehow,
numerically.) This gives a crude estimate for the cross-over point between Strassen’s algorithm and
the standard matrix multiplication algorithm.
2. Implement your variant of Strassen’s algorithm and the standard matrix multiplication algorithm to
find the cross-over point experimentally. Experimentally optimize for n0 and compare the experimen-
tal results with your estimate from above. Make both implementations as efficient as possible. The
actual cross-over point, which you would like to make as small as possible, will depend on how effi-
1
ciently you implement Strassen’s algorithm. Your implementation should work for any size matrices,
not just those whose dimensions are a power of 2.
To test your algorithm, you might try matrices where each entry is randomly selected to be 0 or 1;
similarly, you might try matrices where each entry is randomly selected to be 0, 1 or 2, or instead 0,