In this assignment, you are expected to implement and profile two Matrix multipl
ID: 3680500 • Letter: I
Question
In this assignment, you are expected to implement and profile two Matrix multiplication algorithm - a simple algorithm that takes n3 time and Strassen’s Algorithm. Both implementations can be assumed to work only with type int. You must run and profile these two implementations using gprof. You need to submit profiler output. Make sure you submit readable output as opposed to gmon.out. Extra points will be given for interpretation of the output. You need to compile and generate executable of the given matrix multiplication implementations in using gcc. You should compile and link with –pg option. gcc and gprof are available on Linux environment.
Explanation / Answer
void multiply(int A[][N], int B[][N], int C[][N])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
C[i][j] = 0;
for (int k = 0; k < N; k++)
{
C[i][j] += A[i][k]*B[k][j];
}
}
}
}
For iterative algorithms, first you need estimate approximately how many instructions each step or statement of the algorithm (pseudocode/program) will need (for one execution of that step). This can be called the instruction count. You can assume at a high level that addition, multiplication, assignment operation, function calls etc. can be done in a single instruction (though in reality, this might not always be the case, such as when operating on big integers). If a step contains a function call, you must count both the function call instruction as well as time complexity of the called function, which can be obtained by doing this same process on that function. Unless it is some pre-defined function like printf(), in which case you can at best assume some constant time complexity.
DandC-Matrix-Multiply(M1, M2)
A := new matrix from top left part of M1
B := new matrix from top right part of M1
C := new matrix from bottom left part of M1
.............................
E := new matrix from top left part of M2
.............................
H:= new matrix from bottom right part of M2
P := Matrix-Add(DandC-Matrix-Multiply(A, E),
DandC-Matrix-Multiply(B, G))
Q := Matrix-Add(DandC-Matrix-Multiply(A, F),
DandC-Matrix-Multiply(B, H))
R := Matrix-Add(DandC-Matrix-Multiply(C, E),
DandC-Matrix-Multiply(D, G))
S := Matrix-Add(DandC-Matrix-Multiply(C, F),
DandC-Matrix-Multiply(D, H))
Combine P, Q, R and S into a single matrix M3
Return M3
This basic blockwise divide and conquer matrix multiplication algorithm follows from the definition of matrix multiplication itself.Strassen's algorithm, on the other hand, uses non-obvious mathematical decompositions to bring down the asymptotic complexity to O(nlg7) from O(n3),