使用分而治之的矩陣乘法

問題是，速度非常慢，可怕的慢，即使在小n下，例如：當n = 1024時，一定有什麼問題，有人呢？使用分而治之的矩陣乘法

無論何時函數調用，我都沒有創建新的矩陣C，當基本情況發生時，我將新結果添加到存儲在原始矩陣C中的先前結果。

int **matA,**matB,**matC; 

    void matmul_div_rec(int Arow,int Acol,int Brow,int Bcol,int n) { 
     if(n==1) 
     { 
      matC[Arow][Bcol]+=matA[Arow][Acol]*matB[Brow][Bcol]; 
     } 
     else 
     { 
      matmul_div_rec(Arow+0,Acol+0,Brow+0,Bcol+0,n/2); 
      matmul_div_rec(Arow+0,Acol+n/2,Brow+n/2,Bcol+0,n/2); 
      matmul_div_rec(Arow+0,Acol+0,Brow+0,Bcol+n/2,n/2); 
      matmul_div_rec(Arow+0,Acol+n/2,Brow+n/2,Bcol+n/2,n/2); 
      matmul_div_rec(Arow+n/2,Acol+0,Brow+0,Bcol+0,n/2); 
      matmul_div_rec(Arow+n/2,Acol+n/2,Brow+n/2,Bcol+0,n/2); 
      matmul_div_rec(Arow+n/2,Acol+0,Brow+0,Bcol+n/2,n/2); 
      matmul_div_rec(Arow+n/2,Acol+n/2,Brow+n/2,Bcol+n/2,n/2); 
     } 
     return; } 
int main() 
{ 
    matmul_div_rec(0,0,0,0,n); //n must be the power of 2 

}

來源

2017-07-01 B. Jack

鑑於矩陣的大小，我猜測它們是稀疏矩陣（大多爲零）。如果你這樣對待他們，你可以節省大量的時間和空間。 – doron

閱讀有關strassen乘法矩陣的方法，https://stackoverflow.com/questions/4846938/divide-and-conquer-matrix-multiplication http://www.geeksforgeeks.org/strassens-matrix-multiplication/ http：/ /www.geeksforgeeks.org/strassens-matrix-multiplication/ – EsmaeelE

請參閱https://stackoverflow.com/questions/12922031/recursive-matrix-multiplication –

文簡要討論，例如，this紙，Strassen的算法的實現（即使它是正確的）具有隻有在使用一些額外的想法有競爭力的表現。這些包括例如使用所謂的Morton order佈局來存儲內存中的矩陣，以獲得更容易的方式來解決子表並通過更好的存儲器局部性來改進緩存行爲。此外，通過在遞歸的基本情況下使用SIMD來並行化矩陣加法，可能會有改進。

來源

2017-07-01 10:01:47 Codor

問題中的代碼不是Strassen。這是一種以「分而治之」遞歸風格編寫的樸素矩陣乘法算法。 –

使用分而治之的矩陣乘法

回答

相關問題