CECS 524 Project 2
Implement the  Strassen matrix multiplication using Rinda (on a Beowulf 
cluster, if available).
Due Monday October 29

 
You can read about the Strassen algorithm on pages 47-50 of Algorithms and 
Complexity by Herbert S. Wilf found at
http://www.math.upenn.edu/%7Ewilf/AlgoComp.pdf
The algorithm is recursive with an nxn matrix multiplication requiring 
seven n/2 x n/2 multiplications.  Use only matrices where n is a power of 
2.

Develop the solution in stages.  
1. Implement Strassen using the Ruby library Matrix class for the seven 
n/2 x n/2 multiplications.  Test with n=16.  Use the Matrix class to compute 
the n x n result for comparison. (Just compare one entry.) This step 
checks that you copied the algorithm correctly.

2. Change step 1 to use recursion.

3. Change step 2 to use the Matrix class multiplication if n < 100.  Test 
with n = 128. (The recursion overhead dominates for smaller n.)

4. Modify step 3 to use Rinda. Note you cannot pass a Matrix as a field in a 
tuple.  But you can pass the row vectors, so pass a vector of row vectors. 
The Matrix.rows method creates a Matrix from its rows. The to_a method 
makes an array of rows from a Matrix.
 
An initiator will write the original multiplication problem and take the 
result. A generator program will read a multiplication tuple and either do 
the computation if n < 100 or generate the seven tuples for the n/2 problems. 
If it does the computation it writes a result tuple.  An integrator 
program will take the seven n/2 result tuples and produce and write the n 
result. You can't really match row vectors. Add a unique ID to each tuple 
for the matching. I used a scheme where if the parent had id p the seven 
children had ids 10p+1 through 10p+7.    


Submit the code for the final Rinda solution.  It should not be long. My 
three Strassen files total 118 lines excluding comments. Show a run of a 
256x256 matrix with random real data, comparing one entry with its result 
using the Matrix class.  If Beowulf is available we can try larger 
matrices. Even if not, it is interesting to see how to use Rinda 
effectively to avoid bottlenecks, but it is not required for this 
assignment. At some point you might need to change the load limit.  The 
default is 25,000,000.  I used 100,000,000 by adding the line
DRb::DRbServer.default_load_limit(100000000)


The CECS Linux machines are available for testing Rinda.  To use them 
remotely telnet or ssh to heart.cecs.csulb.edu and rlogin linux.  Upload 
files to the htdocs folder on heart.