分而治之矩陣乘法

我很難得到分而治之的矩陣乘法運行。據我瞭解，你分割尺寸爲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

分而治之矩陣乘法

回答

相關問題