Strassen's algorithm

Static Badge

Implement the Strassen's alorithm for multiplying matrices. You can assume the matrices are the same size and quadratic. For a more detailed explanation refer to http://en.wikipedia.org/wiki/Strassen_algorithm.

Implementation guidelines

  1. Running the program:

    • The program can be ran in different modes (sequential, parallel and distributed) by specifying a parameter.

    • User can specify the size of the matrices.

    • The program measures run-time needed to complete.

  2. Problem specific implementation requirements

    • The values in the matrices are random.

    • The implementation must adapt automatically to the hardware it is being ran on (Physical CPU's, Cores, Memory, etc..);

Testing

All three implementations should be tested. The parameter that influences the run-time is the size of the matrices. All three implementations should be tasted using the same matrices per configuration. Start the test with the size of matrices set to 500. Obtain the next configuration by increasing the size of the matrices by 500. Testing should stop once the sequential version requires more then 10 minutes to compute. Each configuration should be tested with a specific version of the implementation at least three times. The average running time should be considered as the result. Test all three implantations using the same matrices for input to produce comparable results.\ Results should be included in a text file (CSV format). The fields should are:\ \((size, sequential, paralell, distributed)\).

Present the results in your report using numeric and graphical representation. Discuss the results and explain them in detail.