分治矩阵乘法

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

Classical:

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[][]类型的，经典方法是传统的三重循环矩阵乘法。

- Raptrex

---

为什么你想用这种方式进行矩阵乘法？如果你对性能有兴趣，那么肯定有数值库可用，比你自己写的快得多，而且时间也合理。如果你对数字计算感兴趣，我建议从循环分块开始学习（维基百科有一篇文章），而不是递归解决方案。 - Samsdram

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

- Null Set

Answer 2

有人能告诉我我的分治算法哪里出了问题吗？

可以的：

   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)

这是不正确的。

1. 首先，删除divideAndConquer()调用，并将a/b/c/d替换为topLeft/topRight等。看看是否会给出正确的结果。

2. 您的divideAndConquer()方法需要一对输入参数，因此您可以使用A*B。一旦您完成了这项工作，请摆脱对classical()的调用，改用divideAndConquer()。（或者将它们保存在长度不是2的倍数的矩阵中。）

- Jason S

Answer 3

以下是一些尝试调试的方法：

• 尝试使用一些非常简单的测试矩阵作为输入（例如全为零，只有一个或少数几个关键点为一）。你可能会看到“失败”的模式，从而确定错误所在。

• 确保你的“经典”方法可以给出正确的答案。对于小矩阵，可以使用在线工具Wolfram Alpha来测试答案：http://www.wolframalpha.com/examples/Matrices.html

• 调试递归：在函数入口和出口处添加printf()语句，包括调用参数。运行你的测试矩阵，将输出写入日志文件，并用文本编辑器打开日志文件。逐步检查每种情况，在编辑器旁边写下你的注释，确保每一步都正确。如果需要，可以添加更多的printf() 语句并重新运行。

祝你完成作业顺利！

- payne

---

我的经典方法确实能给我正确的答案。我会尝试制作一个全是1的矩阵，而不是0，因为我怀疑一个全是0的矩阵不会起作用，因为加上或乘以0都会得到0。 - Raptrex

是的，全零矩阵将给出零。但添加一些策略性的1（如在一列或行或对角线中全部为1）将给您一些更好的测试。 - payne

Answer 4

你可能会发现维基百科上Strassen算法的文章有所帮助。

- Charlie Martin

---

我接下来将实现Strassen算法，但我也需要分治。 - Raptrex