斯特(te)拉(la)森矩陣乘法簡介
時間：2018-08-15 來(lai)源：未(wei)知
二維(wei)數組(zu)無論在數值計(ji)算(suan)(suan)領域(yu)還是(shi)在非數值計(ji)算(suan)(suan)領域(yu)都是(shi)一(yi)種相當基本(ben)(ben)、重要(yao)且抽象的(de)(de)數據結構(gou)。二維(wei)數組(zu)在數學中(zhong)的(de)(de)表(biao)現形式是(shi)矩陣(zhen)，因此研究 矩陣(zhen)的(de)(de)基本(ben)(ben)運(yun)(yun)算(suan)(suan)本(ben)(ben)質上(shang)就是(shi)在研究二維(wei)數組(zu)的(de)(de)運(yun)(yun)算(suan)(suan)。顯然，盡可(ke)能地提高矩陣(zhen)運(yun)(yun)算(suan)(suan)速(su)率對(dui)于編(bian)程而言是(shi)十分(fen)重要(yao)的(de)(de)工作(zuo)。
矩陣加法和矩陣乘(cheng)法是(shi)矩陣中基本的(de)矩陣運(yun)算。設A、B是(shi)兩(liang)個n×n的(de)矩陣。矩陣的(de)加法表示(shi)兩(liang)個矩陣對應位(wei)置元素之和，因此它們(men)的(de)和仍(reng)然(ran)是(shi)一 個n×n的(de)矩陣，記為(wei)C=A+B。顯然(ran)，矩陣加法的(de)時間復雜(za)度為(wei)O(n2)。
如果設矩(ju)陣(zhen)A與B的(de)(de)乘積為(wei)矩(ju)陣(zhen)C，即C=A×B，顯然(ran)矩(ju)陣(zhen)C也是一(yi)個n×n的(de)(de)矩(ju)陣(zhen)。則(ze)矩(ju)陣(zhen)C的(de)(de)第i行第j列的(de)(de)元(yuan)素C(I,j)等(deng)于矩(ju)陣(zhen)A的(de)(de)第i行和矩(ju)陣(zhen)B的(de)(de)第j 列對應(ying)元(yuan)素乘積的(de)(de)和。可表示為(wei)：
按(an)這個公式計算C(i,j)需要n次乘(cheng)法(fa)與(yu)n-1次加法(fa)，而矩(ju)(ju)(ju)陣C中有n×n個元(yuan)素，因此，由矩(ju)(ju)(ju)陣乘(cheng)法(fa)定(ding)義而直接產生的矩(ju)(ju)(ju)陣相乘(cheng)算法(fa)時間(jian)復雜(za)度為(wei)O(n3) 。
人(ren)們長期對矩陣的乘法(fa)計算(suan)(suan)的改(gai)進工作(zuo)做著不(bu)懈的努(nu)力(li)，做出不(bu)少嘗試，也試圖設(she)計或(huo)改(gai)進這個(ge)算(suan)(suan)法(fa)，但(dan)無論(lun)怎樣改(gai)進都(dou)囿于(yu)O(n3)數量級的時(shi)間 復雜度(du)，沒(mei)有顯著地提速。
1969年，斯(si)特拉(la)森（V.Strassen）利用分治策(ce)略并加上(shang)數(shu)學處理設計出了(le)一(yi)種時間復雜度是O(n2.81)（準確地說是O(nlog7)）的(de)矩(ju)陣(zhen)相乘算法，宣 稱在時間復雜度數(shu)量(liang)級上(shang)有所突(tu)破。此(ci)結果一(yi)發布，立即震動了(le)整個數(shu)學界。
為簡單描述(shu)這一算法，我們(men)假定矩(ju)陣(zhen)C的(de)(de)(de)階數是2的(de)(de)(de)冪(mi)，即存在一個非負正數k使得n=2k。若n不(bu)是2的(de)(de)(de)冪(mi)，則可通過適當(dang)添加全零行和全零列(lie)來構造 成(cheng)2的(de)(de)(de)冪(mi)的(de)(de)(de)方陣(zhen)。
按照分治策略，首先將矩陣A與B分解(jie)成(cheng)4個(n/2)×(n/2)矩陣，即：
對A和(he)B每(mei)個(n/2)×(n/2)矩陣(zhen)(zhen)進行矩陣(zhen)(zhen)乘法運算即可(ke)得到(dao)C。其中(zhong)：
C11=A11B11+A12B21
C12=A11B12+A12B22
C21=A21B11+A22B21
C22=A21B12+A22B22
使用(yong)(yong)通常(chang)的(de)(de)矩(ju)(ju)陣(zhen)(zhen)(zhen)(zhen)乘(cheng)法(fa)與(yu)加法(fa)計算(suan)分(fen)(fen)別(bie)得到C11、C12、C21、C22四個子(zi)矩(ju)(ju)陣(zhen)(zhen)(zhen)(zhen)，那么顯然(ran)可(ke)(ke)以(yi)(yi)得出分(fen)(fen)塊子(zi)矩(ju)(ju)陣(zhen)(zhen)(zhen)(zhen)拼接后(hou)的(de)(de)矩(ju)(ju)陣(zhen)(zhen)(zhen)(zhen)就是矩(ju)(ju)陣(zhen)(zhen)(zhen)(zhen)C。如(ru)果(guo)分(fen)(fen)塊子(zi)矩(ju)(ju)陣(zhen)(zhen)(zhen)(zhen)階 數仍然(ran)大于(yu)2，則(ze)可(ke)(ke)繼(ji)續用(yong)(yong)此方(fang)式將分(fen)(fen)塊子(zi)矩(ju)(ju)陣(zhen)(zhen)(zhen)(zhen)劃分(fen)(fen)為更小的(de)(de)4塊，直至每個子(zi)矩(ju)(ju)陣(zhen)(zhen)(zhen)(zhen)都只有1個元素以(yi)(yi)至于(yu)可(ke)(ke)以(yi)(yi)直接計算(suan)其乘(cheng)積為止。對于(yu)使用(yong)(yong)分(fen)(fen)塊子(zi)矩(ju)(ju) 陣(zhen)(zhen)(zhen)(zhen)計算(suan)C的(de)(de)方(fang)法(fa)，顯然(ran)需要8次乘(cheng)法(fa)與(yu)4次加法(fa)，由(you)于(yu)每兩(liang)個n/2級(ji)方(fang)陣(zhen)(zhen)(zhen)(zhen)的(de)(de)計算(suan)都可(ke)(ke)以(yi)(yi)在某(mou)個可(ke)(ke)預見的(de)(de)時間cn2（c是常(chang)數）內完成，則(ze)通過分(fen)(fen)治法(fa)我們可(ke)(ke) 以(yi)(yi)得到T(n)的(de)(de)遞(di)歸表示方(fang)法(fa)：
其(qi)中b和d是兩個常數。求解這個遞歸關系式：
可(ke)以看(kan)出，這(zhe)種方(fang)式與通常的(de)矩陣乘(cheng)法計算(suan)時間(jian)復雜度(du)一樣。究其原因(yin)，這(zhe)種方(fang)法仍然是使用8次(ci)乘(cheng)法與4次(ci)加(jia)法。若無法有效降低(di)乘(cheng)法的(de)次(ci)數，則(ze)仍 然無法有效降低(di)時間(jian)復雜度(du)。
斯特拉(la)森在(zai)分治法的(de)基礎上，設計(ji)出了一(yi)種7次乘(cheng)法的(de)處(chu)理方(fang)式。其處(chu)理方(fang)式是：先使用(yong)7個(ge)乘(cheng)法10個(ge)加法計(ji)算7個(ge)等式：
P=(A11+A22)(B11+B22)
Q=(A21+A22)B11
R=A11(B12-B22)
S=A22(B21-B11)
T=(A11+A12)B22
U=(A21-A11)(B11+B12)
V=(A12-A22)(B21+B22)
然(ran)后使(shi)用8個加法將這(zhe)7個等(deng)式構造成C：
C11=P+S-T+V
C12=R+T
C21=Q+S
C22=P+R-Q+U
以上共使(shi)用7次(ci)乘法(fa)與18次(ci)加(jia)法(fa)。
則由T(n)所得的遞歸公(gong)式是：
推導(dao)時間復(fu)雜(za)度的過程(cheng)類似(si)上(shang)文，這里不再贅述。終可得時間復(fu)雜(za)度為O(nlog7)≈O(n2.81)。
在斯特拉森(sen)之后，許多人也試圖繼續(xu)改進該算法(fa)。其中(zhong)，J.E.Hopcroft和(he)L.R.Kerr已(yi)經證明，兩(liang)個(ge)2的(de)(de)冪階矩陣(zhen)相(xiang)乘必(bi)須(xu)要使(shi)用7次乘法(fa)無法(fa)再簡化。 若想(xiang)再進一步(bu)簡化則必(bi)須(xu)考慮(lv)劃分為3的(de)(de)冪或4的(de)(de)冪以及(ji)更(geng)高級的(de)(de)冪階才(cai)有意義。因此分治策(ce)略必(bi)須(xu)改變，即必(bi)須(xu)采取其他分治策(ce)略的(de)(de)設計思路才(cai)行。
后(hou)需(xu)要說明的是，斯(si)特(te)拉(la)森(sen)矩陣(zhen)乘法(fa)目前只有(you)理論(lun)意義。事實證明當矩陣(zhen)階數足夠大（n在128階以上）時，它和普通的矩陣(zhen)乘法(fa)的執行時間仍無顯 著(zhu)差別。即使如此，斯(si)特(te)拉(la)森(sen)矩陣(zhen)乘法(fa)給(gei)我們提供了一個有(you)益(yi)的啟示：即使從(cong)簡單的定義出發來設計的算(suan)法(fa)也可能(neng)不是好的，仍然(ran)可以去優化。
參考文獻：
[1]《線(xian)性代數與多項式的(de)快速算(suan)法》
[2]《計算機(ji)算法(fa)基礎（第三版）》
