矩阵乘法的分而治之

发布于 2024-10-14 18:59:02 字数 636 浏览 2 评论 0原文

我无法让分而治之的矩阵乘法发挥作用。根据我的理解，你将大小为 nxn 的矩阵分成象限（每个象限为 n/2），然后你会这样做：

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

我的分而治之的输出非常大，我很难弄清楚问题，因为我不是非常适合递归。

示例输出：

原始矩阵 A：

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

原文

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.

example output:

Original Matrix A:

A x A

Classical:

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

Divide and Conquer:

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

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

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

谷夏 2024-10-21 18:59:02

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

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.

It should look something like this:

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

回复收藏 0 原文

在你怀里撒娇 2024-10-21 18:59:02

一些可以尝试的调试方法：

尝试一些非常简单的测试矩阵作为输入（例如全零，带有一个或几个策略性的矩阵）。您可能会在“失败”中看到一种模式，该模式将向您显示错误所在。
确保您的“经典”方法能够为您提供正确的答案。对于小型矩阵，您可以在线使用 Woflram Alpha 来测试答案：http://www.wolframalpha .com/examples/Matrices.html
要调试递归：在函数的入口和出口添加 printf() 语句，包括调用参数。运行测试矩阵，将输出写入日志文件，然后使用文本编辑器打开日志文件。逐步完成每个案例，在编辑器中写下注释，确保每一步都能正常工作。添加更多 printf() 语句，并根据需要再次运行。

祝作业顺利！

回复收藏 0 原文

痴情 2024-10-21 18:59:02

有人可以告诉我我在分而治之方面做错了什么吗？

是的：

   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() 调用，并用 topLeft/topRight/etc 替换 a/b/c/d。
看看它是否给出了正确的结果。
您的 divideAndConquer() 方法需要一对输入参数，因此您可以使用 A*B。一旦你开始工作，就不再需要调用 classical()，而是使用 divideAndConquer() 来代替。（或者将它们保存为长度不是 2 倍数的矩阵。）

Could someone tell me what I am doing wrong for divide and conquer?

Yes:

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

You are going through an extra multiplication step here: you shouldn't be calling both divideAndConquer() and classical().

What you are effectively doing is:

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)

which is not correct.

First, remove the divideAndConquer() calls, and replace a/b/c/d by topLeft/topRight/etc.
See if it gives you the proper results.
Your divideAndConquer() method needs a pair of input parameters, so you can use A*B. Once you get that working, get rid of the calls to classical(), and use divideAndConquer() instead. (or save them for matrices that are not a multiple of 2 in length.)

回复收藏 0 原文