- #1
Evales
- 53
- 0
Problem Statement
We are asked to use the following divide and conquer algorithm to get the solution for the multiplication of some matrix A and some matrix B. (See below)
Consider the matrix sizes. Comment the total computational time used on the following three algorithms, when different array sizes (say from 4 to 20) are used. Are they similar? Explain your finding.
- Classic matrix multiplication
- Divide and Conquer
- Strassen’s matrix method
We are using matlab.
Attempt at solutions
I have been able to get this divide and conquer code working for a 2x2 matrix and a 4x4 matrix.
2x2 was easy,
4x4 I used the reshape command and horizontal concatenation of parts of the reshaped matrix to build the parts of the 2x2 matrices and then used my previous 2x2 method.
But there is no way I'm going to do that for a 20x20 matrix, let alone all the matrices in between. I have tried looking for methods of splitting matrices evenly online but I keep coming up with very specific methods that don't work if you change the value of 'n'.
Is there anything anyone can suggest that will help me do this so that I can measure the computational time?
PS. As an aside I know that technically Divide and Conquer = Classic method. However our course focuses a lot on actual computational times, rather than just the theoretical times.
Any help is much appreciated.
We are asked to use the following divide and conquer algorithm to get the solution for the multiplication of some matrix A and some matrix B. (See below)
Consider the matrix sizes. Comment the total computational time used on the following three algorithms, when different array sizes (say from 4 to 20) are used. Are they similar? Explain your finding.
- Classic matrix multiplication
- Divide and Conquer
- Strassen’s matrix method
We are using matlab.
Attempt at solutions
I have been able to get this divide and conquer code working for a 2x2 matrix and a 4x4 matrix.
2x2 was easy,
4x4 I used the reshape command and horizontal concatenation of parts of the reshaped matrix to build the parts of the 2x2 matrices and then used my previous 2x2 method.
But there is no way I'm going to do that for a 20x20 matrix, let alone all the matrices in between. I have tried looking for methods of splitting matrices evenly online but I keep coming up with very specific methods that don't work if you change the value of 'n'.
Is there anything anyone can suggest that will help me do this so that I can measure the computational time?
PS. As an aside I know that technically Divide and Conquer = Classic method. However our course focuses a lot on actual computational times, rather than just the theoretical times.
Any help is much appreciated.
Attachments
Last edited:
