algorithm - 分而治之矩阵乘法

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×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 for 循环矩阵乘法

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