Divide and Conquer Matrix Multiplication
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
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
}
}
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 moreprintf()
statements and run again if needed.
Good luck with the homework!
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 toclassical()
, and usedivideAndConquer()
instead. (or save them for matrices that are not a multiple of 2 in length.)
You might find the Wiki article on Strassen's algorithm helpful.
精彩评论