色偷偷偷亚洲综合网另类,亚洲欧美另类在线观看,欧美午夜激情在线,久久久精品一区

二維數(shù)組無論在數(shù)值計算領(lǐng)域還是在非數(shù)值計算領(lǐng)域都是一種相當(dāng)基本、重要且抽象的數(shù)據(jù)結(jié)構(gòu)。二維數(shù)組在數(shù)學(xué)中的表現(xiàn)形式是矩陣，因此研究 矩陣的基本運(yùn)算本質(zhì)上就是在研究二維數(shù)組的運(yùn)算。顯然，盡可能地提高矩陣運(yùn)算速率對于編程而言是十分重要的工作。

矩陣加法和矩陣乘法是矩陣中基本的矩陣運(yùn)算。設(shè)A、B是兩個n×n的矩陣。矩陣的加法表示兩個矩陣對應(yīng)位置元素之和，因此它們的和仍然是一 個n×n的矩陣，記為C=A+B。顯然，矩陣加法的時間復(fù)雜度為O(n2)。

如果設(shè)矩陣A與B的乘積為矩陣C，即C=A×B，顯然矩陣C也是一個n×n的矩陣。則矩陣C的第i行第j列的元素C(I,j)等于矩陣A的第i行和矩陣B的第j 列對應(yīng)元素乘積的和。可表示為：

按這個公式計算C(i,j)需要n次乘法與n-1次加法，而矩陣C中有n×n個元素，因此，由矩陣乘法定義而直接產(chǎn)生的矩陣相乘算法時間復(fù)雜度為O(n3) 。

人們長期對矩陣的乘法計算的改進(jìn)工作做著不懈的努力，做出不少嘗試，也試圖設(shè)計或改進(jìn)這個算法，但無論怎樣改進(jìn)都囿于O(n3)數(shù)量級的時間 復(fù)雜度，沒有顯著地提速。

1969年，斯特拉森（V.Strassen）利用分治策略并加上數(shù)學(xué)處理設(shè)計出了一種時間復(fù)雜度是O(n2.81)（準(zhǔn)確地說是O(nlog7)）的矩陣相乘算法，宣 稱在時間復(fù)雜度數(shù)量級上有所突破。此結(jié)果一發(fā)布，立即震動了整個數(shù)學(xué)界。

為簡單描述這一算法，我們假定矩陣C的階數(shù)是2的冪，即存在一個非負(fù)正數(shù)k使得n=2k。若n不是2的冪，則可通過適當(dāng)添加全零行和全零列來構(gòu)造 成2的冪的方陣。

按照分治策略，首先將矩陣A與B分解成4個(n/2)×(n/2)矩陣，即：

對A和B每個(n/2)×(n/2)矩陣進(jìn)行矩陣乘法運(yùn)算即可得到C。其中：

C11=A11B11+A12B21

C12=A11B12+A12B22

C21=A21B11+A22B21

C22=A21B12+A22B22

使用通常的矩陣乘法與加法計算分別得到C11、C12、C21、C22四個子矩陣，那么顯然可以得出分塊子矩陣拼接后的矩陣就是矩陣C。如果分塊子矩陣階 數(shù)仍然大于2，則可繼續(xù)用此方式將分塊子矩陣劃分為更小的4塊，直至每個子矩陣都只有1個元素以至于可以直接計算其乘積為止。對于使用分塊子矩 陣計算C的方法，顯然需要8次乘法與4次加法，由于每兩個n/2級方陣的計算都可以在某個可預(yù)見的時間cn2（c是常數(shù)）內(nèi)完成，則通過分治法我們可 以得到T(n)的遞歸表示方法：

其中b和d是兩個常數(shù)。求解這個遞歸關(guān)系式：

可以看出，這種方式與通常的矩陣乘法計算時間復(fù)雜度一樣。究其原因，這種方法仍然是使用8次乘法與4次加法。若無法有效降低乘法的次數(shù)，則仍 然無法有效降低時間復(fù)雜度。

斯特拉森在分治法的基礎(chǔ)上，設(shè)計出了一種7次乘法的處理方式。其處理方式是：先使用7個乘法10個加法計算7個等式：

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)

然后使用8個加法將這7個等式構(gòu)造成C：

C11=P+S-T+V

C12=R+T

C21=Q+S

C22=P+R-Q+U

以上共使用7次乘法與18次加法。

則由T(n)所得的遞歸公式是：

推導(dǎo)時間復(fù)雜度的過程類似上文，這里不再贅述。終可得時間復(fù)雜度為O(nlog7)≈O(n2.81)。

在斯特拉森之后，許多人也試圖繼續(xù)改進(jìn)該算法。其中，J.E.Hopcroft和L.R.Kerr已經(jīng)證明，兩個2的冪階矩陣相乘必須要使用7次乘法無法再簡化。 若想再進(jìn)一步簡化則必須考慮劃分為3的冪或4的冪以及更高級的冪階才有意義。因此分治策略必須改變，即必須采取其他分治策略的設(shè)計思路才行。

后需要說明的是，斯特拉森矩陣乘法目前只有理論意義。事實(shí)證明當(dāng)矩陣階數(shù)足夠大（n在128階以上）時，它和普通的矩陣乘法的執(zhí)行時間仍無顯 著差別。即使如此，斯特拉森矩陣乘法給我們提供了一個有益的啟示：即使從簡單的定義出發(fā)來設(shè)計的算法也可能不是好的，仍然可以去優(yōu)化。

參考文獻(xiàn)：

[1]《線性代數(shù)與多項式的快速算法》

[2]《計算機(jī)算法基礎(chǔ)（第三版）》