Divide and Conquer Matrix Multiplication

algorithm math matrix multiplication

16,468

Solution 1

You are recursively calling divideAndConquer in the wrong way. What your function does is square a matrix. In order for divide and conquer matrix multiplication to work, it needs to be able to multiply two potentially different matrixes together.

It should look something like this:

private static int[][] divideAndConquer(int[][] matrixA, int[][] matrixB){
    if (matrixA.length == 2){
         //calculate and return base case
    }
    else {
        //make a11, b11, a12, b12 etc. by dividing a and b into quarters      
        int[][] c11 = addMatrix(divideAndConquer(a11,b11),divideAndConquer(a12,b21));
        int[][] c12 = addMatrix(divideAndConquer(a11,b12),divideAndConquer(a12,b22));
        int[][] c21 = addMatrix(divideAndConquer(a21,b11),divideAndConquer(a22,b21));
        int[][] c22 = addMatrix(divideAndConquer(a21,b12),divideAndConquer(a22,b22));
        //combine result quarters into one result matrix and return
    }
}

Solution 2

Some debugging approaches to try:

Try some very simple test matrices as input (e.g. all zeros, with a one or a few strategic ones). You may see a pattern in the "failures" that will show you where your error(s) are.
Make sure your "classical" approach is giving you correct answers. For small matrices, you can use Woflram Alpha on-line to test answers: http://www.wolframalpha.com/examples/Matrices.html
To debug recursion: add printf() statements at the entry and exit of your function, including the invocation arguments. Run your test matrix, write the output to a log file, and open the log file with a text editor. Step through each case, writing your notes alongside in the editor making sure it's working correctly at each step. Add more printf() statements and run again if needed.

Good luck with the homework!

Solution 3

Could someone tell me what I am doing wrong for divide and conquer?

Yes:

   int[][] a = divideAndConquer(topLeft);
   int[][] b = divideAndConquer(topRight);
   int[][] c = divideAndConquer(bottomLeft);
   int[][] d = divideAndConquer(bottomRight);

   int[][] c11 = addMatrix(classical(a,a),classical(b,c));
   int[][] c12 = addMatrix(classical(a,b),classical(b,d));
   int[][] c21 = addMatrix(classical(c,a),classical(d,c));
   int[][] c22 = addMatrix(classical(c,b),classical(d,d));

You are going through an extra multiplication step here: you shouldn't be calling both divideAndConquer() and classical().

What you are effectively doing is:

C11 = (A11^2)⋅(B11^2) + (A12^2)⋅(B21^2)
C12 = (A11^2)⋅(B12^2) + (A12^2)⋅(B22^2)
C21 = (A21^2)⋅(B11^2) + (A22^2)⋅(B21^2)
C22 = (A21^2)⋅(B12^2) + (A22^2)⋅(B22^2)

which is not correct.

First, remove the divideAndConquer() calls, and replace a/b/c/d by topLeft/topRight/etc. See if it gives you the proper results.
Your divideAndConquer() method needs a pair of input parameters, so you can use A*B. Once you get that working, get rid of the calls to classical(), and use divideAndConquer() instead. (or save them for matrices that are not a multiple of 2 in length.)

Solution 4

You might find the Wiki article on Strassen's algorithm helpful.

View more solutions

16,468

Author by

Raptrex

Updated on July 25, 2022

Comments

Raptrex almost 2 years
I am having trouble getting divide and conquer matrix multiplication to work. From what I understand, you split the matrices of size nxn into quadrants (each quadrant is n/2) and then you do:
```
C11 = A11⋅ B11 + A12 ⋅ B21   
C12 = A11⋅ B12 + A12 ⋅ B22  
C21 = A21 ⋅ B11 + A22 ⋅ B21  
C22 = A21 ⋅ B12 + A22 ⋅ B22  
```
My output for divide and conquer is really large and I'm having trouble figuring out the problem as I am not very good with recursion.

example output:

Original Matrix A:
```
4 0 4 3   
5 4 0 4   
4 0 4 0  
4 1 1 1 
```
A x A

Classical:
```
44 3 35 15  
56 20 24 35  
32 0 32 12  
29 5 21 17  
```
Divide and Conquer:
```
992 24 632 408  
1600 272 720 1232   
512 0 512 384  
460 17 405 497  
```
Could someone tell me what I am doing wrong for divide and conquer? All my matrices are int[][] and classical method is the traditional 3 for loop matrix multiplication
Raptrex about 13 years

I will be implementing Strassens algorithm next, but I need divide and conquer as well.
Raptrex about 13 years

my classical approach does give me the right answers. I'll try making a matrix of all 1s instead of 0 because I doubt that a matrix of 0s will work since adding or multiplying with 0 will be 0.
payne about 13 years

Yes, a matrix of all zeros will give you zero. But add a FEW strategic ones, (like all in one column or row or diagonal) will give you some better tests.