斯特拉森矩陣乘法

1969年斯特拉森利用分治策略並加上一些處理技巧設計出一種矩陣乘法。
為了得到2矩陣相乘的分治算法1、定義一個小問題,並指明那個問題如何進行乘法運算,2、確定一個大問題,進行劃分,如何指明對這些小問題進行乘法運行。
設A和B是倆個n x n的矩陣,其中n可以寫成2的冪。將A和B分別等分成4個小矩陣,此時如果把A和B都當成2x2矩陣來看,每個元素就是一個(n/2)x(n/2)矩陣,而A和B的成積就可以寫成〔A11 A12〕[B11 B12] [C11 C12]
X =
[A21 A22] [B21 B22 ] [c21 C22]
其中 利用斯特拉森方法得到7個小矩陣,分別定義為:
m1=(A12=A22)(B21+B22)
m2=(A11+A22)(B11+B22)
m3=(A11-A21)(B11+B12)
M4=(A11+A12)B22
M5=A11(B12-B22)
M6=A22(B21-B11)
M7=(A21+A22)B11
矩陣m1~m7可以通過7次矩陣乘法、6次矩陣加法和4次矩陣減法計算得出,前述4個小矩陣可以由矩陣m1~m7,通過6次矩陣加法和2次矩陣減法得出,方法如下:
c11=m6+m1+m2-m4
c12=m5+m4
c21=m6+m7
c22=m5-m3+m2-m1
用上述方案解n=2;矩陣乘法;假定施特拉斯矩陣分割方案僅用於n>=8的矩陣乘法,而對於小於8的矩陣直接利用公式計算;n的值越大,斯拉特森方法更方便;設T(n)表示斯特拉森分治運算法所需時間,因為大的矩陣會被遞歸分成小矩陣直到每個矩陣的大小小於或等於k,所以T(n)的遞歸表達式為T(n)=d(n<=k);T(n)=7*t(n/2)+cn2(n平方)(n>k),其中cn2表示完成18次(n/2)(n/2)接矩陣的加減法,以及把大小為N的矩陣分割成小矩陣所需的時間;

相關詞條

熱門詞條

聯絡我們