Divide and Conquer, Matrix Multiplication MATLAB

  • Thread starter Evales
  • Start date
  • #1
54
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.
 

Attachments

  • Screen Shot 2013-04-12 at 12.15.30 PM.png
    Screen Shot 2013-04-12 at 12.15.30 PM.png
    42.2 KB · Views: 803
Last edited:

Answers and Replies

  • #2
54
0
If there is any reason in particular that people find it difficult to answer my question, please let me know. I would be more than happy to provide additional information, and I would hugely grateful to anyone who could offer to help.
 

Related Threads on Divide and Conquer, Matrix Multiplication MATLAB

  • Last Post
Replies
7
Views
2K
Replies
16
Views
4K
  • Last Post
Replies
8
Views
4K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
10
Views
1K
Replies
5
Views
3K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
3
Views
28K
Top