Divide and Conquer Matrix Multiplication

Question

I am having problems dividing and multiplying matrix multiplication by 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 conclusion for divide and conquer is really great, and I had trouble figuring out the problem, as I am not very good at recursion.

Output Example:

Original matrix A:

 4 0 4 3 5 4 0 4 4 0 4 0 4 1 1 1 

A x A

Classic:

 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 

Can someone tell me what I am doing wrong to divide and win? All my matrices are int[][] , and the classic method is the traditional three-dimensional matrix multiplication

Answer 1

You recursively call divideAndConquer incorrectly. What your function does is a square matrix. In order to split and break matrix multiplication by work, he must be able to multiply two potentially different matrices 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 } } 

Answer 2

Some debugging approaches:

• Try using very simple test matrices as input (for example, all zeros, with one or more strategic ones). You can see the pattern in the “failures” that will show you where your errors are.

• Make sure your “classic” approach gives you the right answers. For small matrices, you can use Woflram Alpha on-line to check answers: http://www.wolframalpha.com/examples/Matrices.html

• Debug recursion: add printf() statements to the entry and exit of your function, including call arguments. Run the test matrix, write the output to the log file and open the log file using a text editor. Go through each case by writing notes next to the editor, making sure that it works correctly at every step. Add additional printf() statements and run again if necessary.

Good luck with your homework!

Answer 3

Can someone tell me what I am doing wrong to divide and win?

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)); 

Here you can perform an additional step of multiplication: you should not call 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 wrong.

• First remove the calls to divideAndConquer() and replace a / b / c / d with topLeft / topRight / etc. See if it gives you the right results.

• Your divideAndConquer() method needs a couple of input parameters, so you can use A * B. Once you get this working, get rid of classical() calls and use divideAndConquer() . (or save them for matrices that are not a multiple of 2 in length.)

Answer 4

You can find the Wiki article in the Strassen algorithm .