分而治之矩阵乘法

我很难得到分而治之的矩阵乘法运行。据我了解，你分割尺寸为n×n的矩阵转换成象限（每个象限为n/2），然后你做：分而治之矩阵乘法

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

我的分而治之的输出实在是大，我无法搞清楚因为我对递归不太好。

示例输出：

原基质A：

甲x一个

古典：

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用于循环矩阵乘法

来源

2011-01-31 Raptrex

为什么你想要做矩阵乘法这样？如果您对原始性能感兴趣，可以使用数字库，我相信它的速度会比您可以在合理的时间内自行编写的速度更快。如果您有兴趣了解数值计算，我将从循环平铺开始（维基百科有一篇文章），而不是递归解决方案。 – Samsdram 2011-01-31 02:03:53

其作业。 – Raptrex 2011-01-31 02:11:36

你递归以错误的方式调用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 
    } 
}

来源

2011-01-31 16:10:51

您可能会发现Wiki文章Strassen's algorithm有帮助。

来源

2011-01-31 01:44:32

接下来我会实施Strassens算法，但我也需要分而治之。 – Raptrex 2011-01-31 01:59:01

一些调试方法尝试：

尝试一些非常简单的测试矩阵作为输入（例如全零，有一个或几个战略性的）。您可能会在“失败”中看到一个模式，它会告诉您错误的位置。
确保您的“经典”方法能够给您正确的答案。对于小矩阵，可以使用Woflram阿尔法上线测试的答案：http://www.wolframalpha.com/examples/Matrices.html
要调试递归：增加你的函数的入口和出口printf()语句，包括调用参数。运行测试矩阵，将输出写入日志文件，然后使用文本编辑器打开日志文件。逐步完成每个案例，在编辑器中编写笔记，确保其在每一步都能正常工作。如果需要，添加更多printf()语句并再次运行。

祝您好运！

来源

2011-01-31 02:42:18 payne

有人能告诉我我做错了分而治之？

是：

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

你正在经历北京多乘步骤：你不应该调用都divideAndConquer()和classical()。

什么你实际上做的是：

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)

这是不正确的。

首先，删除divideAndConquer()呼叫，以及由左上/ topRight /等代替A/B/C/d。看看它是否给你正确的结果。
你divideAndConquer()方法需要对输入参数，所以你可以使用A * B。一旦你得到这个工作，摆脱classical()的呼叫，并使用divideAndConquer()来代替。（或保存他们不在的2长的多个矩阵。）

来源

2011-01-31 13:34:56

分而治之矩阵乘法

回答

相关问题