施特拉森演算法

Template:Onesource 施特拉森演算法（Template:Lang-en）是一個計算矩陣乘法的演算法，時間複雜度為$O(n^{{\log }_{2}7})=O(n^{2.807})$。

簡介

矩陣乘法演算法的演進。

施特拉森演算法在1969年由沃爾克·施特拉森所提出，是第一個時間複雜度低於$O(n^3)$的矩陣乘法演算法。由於演算法簡單理解，且為第一個被提出來的特性，常被演算法教材拿來當作主定理（Template:Lang-en）計算時間複雜度的例子。

另外，因為施特拉森演算法證明了矩陣乘法存在時間複雜度低於$O(n^3)$的演算法，使得更多學者投入研究，尋找更快的演算法。

算法

定義

設$A$、$B$為域$F$上的方矩陣。求兩者的積$C$。一般矩陣可以填0的方法計算令它成為$2^n\times 2^n$矩陣。

$𝐂=𝐀𝐁𝐀,𝐁,𝐂\in F^{2^n\times 2^n}$

計算

將A, B, C分成相等大小的方塊矩陣：

$𝐀=\left[\begin{array}{cc}{𝐀}_{1,1}& {𝐀}_{1,2}\\ {𝐀}_{2,1}& {𝐀}_{2,2}\end{array}\right]\text{ , }𝐁=\left[\begin{array}{cc}{𝐁}_{1,1}& {𝐁}_{1,2}\\ {𝐁}_{2,1}& {𝐁}_{2,2}\end{array}\right]\text{ , }𝐂=\left[\begin{array}{cc}{𝐂}_{1,1}& {𝐂}_{1,2}\\ {𝐂}_{2,1}& {𝐂}_{2,2}\end{array}\right]$

即

${𝐀}_{i,j},{𝐁}_{i,j},{𝐂}_{i,j}\in F^{2^{n-1}\times 2^{n-1}}$

於是

${𝐂}_{1,1}={𝐀}_{1,1}{𝐁}_{1,1}+{𝐀}_{1,2}{𝐁}_{2,1}$

${𝐂}_{1,2}={𝐀}_{1,1}{𝐁}_{1,2}+{𝐀}_{1,2}{𝐁}_{2,2}$

${𝐂}_{2,1}={𝐀}_{2,1}{𝐁}_{1,1}+{𝐀}_{2,2}{𝐁}_{2,1}$

${𝐂}_{2,2}={𝐀}_{2,1}{𝐁}_{1,2}+{𝐀}_{2,2}{𝐁}_{2,2}$

引入新矩陣

${𝐌}_1:=({𝐀}_{1,1}+{𝐀}_{2,2})({𝐁}_{1,1}+{𝐁}_{2,2})$

${𝐌}_2:=({𝐀}_{2,1}+{𝐀}_{2,2}){𝐁}_{1,1}$

${𝐌}_3:={𝐀}_{1,1}({𝐁}_{1,2}-{𝐁}_{2,2})$

${𝐌}_4:={𝐀}_{2,2}({𝐁}_{2,1}-{𝐁}_{1,1})$

${𝐌}_5:=({𝐀}_{1,1}+{𝐀}_{1,2}){𝐁}_{2,2}$

${𝐌}_6:=({𝐀}_{2,1}-{𝐀}_{1,1})({𝐁}_{1,1}+{𝐁}_{1,2})$

${𝐌}_7:=({𝐀}_{1,2}-{𝐀}_{2,2})({𝐁}_{2,1}+{𝐁}_{2,2})$

可得：

${𝐂}_{1,1}={𝐌}_1+{𝐌}_4-{𝐌}_5+{𝐌}_7$

${𝐂}_{1,2}={𝐌}_3+{𝐌}_5$

${𝐂}_{2,1}={𝐌}_2+{𝐌}_4$

${𝐂}_{2,2}={𝐌}_1-{𝐌}_2+{𝐌}_3+{𝐌}_6$

其中$M_{i,j}$的計算也是使用施特拉森演算法求得。

評論

一般矩陣乘法的時間複雜度為$O(n^{{\log }_{2}8})=O(n^3)$，施特拉森演算法因為只有每次的分治法（Template:Lang-en）只有七個矩陣乘法運算，所以依照主定理（Template:Lang-en）可以得出時間複雜度為$O(n^{{\log }_{2}7})=O(n^{2.807})$。但Strassen演算法的數值穩定性較差。

現時時間複雜度最低的矩陣乘法演算法是Coppersmith-Winograd方法的一种扩展方法，其算法复杂度为$O(n^{2.3727}$)。

相關連結

• 矩陣乘法