CECS 524
Strassen Matrix Multiplication

You can read about the Strassen algorithm on pages 47-50 of Algorithms and 
Complexity by Herbert S. Wilf liked from the class site. 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. To make a matrix 
and to check you answer you can use an Erlang matix multiplicaton library. 
matrix.erl, linked from the class site, is a library that represents matrices 
as tuples.

First implement the Strassen algorithm without spawning any processes. As 
helper functions, implement matrix addition and subtraction and a function 
to divide an n x n matrix into four n/2 x n/2 submatrices.  For the latter 
one possiblility is to pass arguments to determine which quarter of the 
original matrix to find. Implement a method to combine the four 
result matrices of size n/2 x n/2 into an n x n matrix.  Use list 
comprehensions when appropriate.
 
Then write another version which creates processes and uses the Beowulf 
cluster.  One approach is to spawn seven processes for the first 
recursive step on seven nodes but to spawn processes on that node 
for the remaining recursive steps. These latter processes will use 
cores on that node. 

Compare timing for the two versions with the same 
data.  For large matrices you can use the library method for matrices of size 
less than 100x100.  Try sizes 128, 256, 512, and 1024.