DSSC - Algorithmic Design - Strassen's Algorithm

This repository contains some code to simplify the implementation and the testing of the Strassen's algorithm for matrix multiplication.

In order to test the differences in term of execution-time between the naive algorithm and the Strassen's algorithm, you need to implement both the algorithms. The former must be implementated by the function naive_matrix_multiplication in the file matrix.c and the latter by the function strassen_matrix_multiplication in the file strassen.c.

A Makefile can be produced by using cmake as follows:

cmake -G "Unix Makefiles" CMakeLists.txt

Afterwards you can compile the code by executing make. This produces an executable named strassen_test which can be executed in POSIX systems by using the command:

./strassen_test 
n Naive Alg.  Strassen's Alg. Same result
1	0.000000	0.000000	1
2	0.000000	0.000000	1
4	0.000000	0.000000	1
8	0.000000	0.000000	1
16	0.000000	0.000000	1
32	0.000000	0.000000	1
64	0.000000	0.000000	1
128	0.000000	0.000000	1
256	0.000000	0.000000	1
512	0.000000	0.000000	1
1024	0.000000	0.000000	1
2048	0.000000	0.000000	1
4096	0.000000	0.000000	1

The first column in the output report the number of the rows and columns in the tested matrixes.

The second and third columns in the output reports the execution-time in seconds of the implementations of the naive algorithm and of the Strassen's algorithm, respectively. Since the two algorithms are not implemented in the repository, strassen_test initially reports 0 seconds for both of them.

Finally, the last column, which is excusively meant to validate the implementations, contains the value 1 if and only if the result of the naive algorithm and that of the Strassen's algorithm are the same.