划分和征服矩阵乘法

Question

我无法分裂并征服矩阵乘法工作.根据我的理解,你将大小为nxn的矩阵分成象限(每个象限是n/2),然后你做:

C11 = A11? B11 + A12 ? B21   
C12 = A11? B12 + A12 ? B22  
C21 = A21 ? B11 + A22 ? B21  
C22 = A21 ? B12 + A22 ? B22  

我的分而治之的输出真的很大,我很难找出问题,因为我对递归并不是很好.

示例输出:

原始矩阵A:

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

A x A

古典:

44 3 35 15  
56 20 24 35  
32 0 32 12  
29 5 21 17  

分而治之:

992 24 632 408  
1600 272 720 1232   
512 0 512 384  
460 17 405 497  

有人能告诉我,我为分而治之做错了吗？我的所有矩阵都是int[][]经典方法,是传统的3循环矩阵乘法

Answer 1

你divideAndConquer以错误的方式递归调用.你的函数做的是对矩阵进行平方.为了使分割和征服矩阵乘法起作用,它需要能够将两个可能不同的矩阵相乘.

它应该看起来像这样:

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
    }
}