CS203B-Adaptive Matrix Multiplication Solved

Part 1 
First read Chapter 4.2 on Strassen’s method for Matrix Multiplication and D’Alberto and Nicolaus paper on adapting the algorithm to use depending on the computer architecture to use Strassen’s algorithm and other methods for multiplying matrices [1].  

 

Part 2 
2a) Write pseudocode for Strassen’s algorithm and the standard square matrix multiply algorithm that runs in Θ(𝑛3).  

2b) Extend the pseudocode of Strassen’s algorithm so that it will work with any value of n (not just n that is a power of 2).

2c) Give a complete a proof of the Asymptotic bounds for the runtime of Strassen’s algorithm and square matrix multiply.

2d) Implement the standard Square Matrix Multiply, Θ(𝑛3), algorithm for matrix multiplication and Strassen’s matrix multiplication algorithm.

 

Part 3 
Conduct an experiment to estimate the constants in the runtime equations of these two algorithms. In this experiment you should use randomly generated square matrices of increasing size with values in the range [-1,1] . Give an estimate from your empirical results for the smallest value of 𝑛 before Strassen’s algorithm becomes more efficient than the Standard algorithm.  

 

Part 4 
Use the code from Part 2 and the result of Part 3 for n to implement a class that provides a simple adaptive method for matrix multiplication. The default value for the threshold for crossing over should be in a config file with default value set based on Part 3. The class should have at least the following 4 public methods:  

-          void calibrate_crossover_point(): Estimates a value for the crossover point for matrix size to decide whether to use Strassen’s approach or the standard approach by running a series of tests of multiplying randomly generated matrices of different sizes. It should save this value to a configuration file.

-          Matrix square_matrix_mutliply(Matrix a, Matrix b): Use the standard approach to mutliply 2 matrices a and b, return their product. 

-          Matrix strassen_mutliply(Matrix a, Matrix b): Use Strassen’s algorithm to multiply 2 matrices a and b, return their product. 

-          Matrix adaptive_multiply(Matrix a, Matrix b): For matrices that are less than the (previously stored or default) crossover point use standard matrix multiplication, for matrices that are greater than the crossover point use Strassen’s method.   

 

Provide an evaluation result extending the results from Part 3 to describe the performance of your implementation of the adaptive_mutliply method.

 

Additional Requirements for the matrix implementation: 

The matrix implementation should be suitable for dense matrices. You are required to define a class Matrix that will be used in the implementation. This class Matrix will represent a matrix in “row-major” order (i.e. for an 𝑛×𝑛-matrix the first row will be stored in an array at index 0 to index n-1 the next row at n to 2n-1 and so on). The class should provide a constructor and methods to get and set the element at any row column index.