分而治之矩阵乘法 [英] Divide and Conquer Matrix Multiplication

问题描述

我有麻烦分而治之矩阵乘法工作。据我了解，你分割大小为N×N矩阵为象限（每个象限为n / 2），然后你做的：

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.

例如输出：

原矩阵A：

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

一个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 for循环矩阵相乘

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

推荐答案

正在递归调用 divideAndConquer 在错误的道路。你的函数的作用是方形矩阵。为了分而治之矩阵乘法的工作，它需要能够将两个潜在的不同矩阵在一起。

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.

这应该是这个样子：

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

这篇关于分而治之矩阵乘法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！