[科普中國]-施特拉森算法

施特拉森算法（英語：Strassen algorithm）是一個計算矩陣乘法的算法。

簡介矩陣乘法算法的演進。

施特拉森算法在1969年由Volker Strassen提出來，是第一個時間復雜度低于{\displaystyle O(n^{3})}的矩陣乘法算法。由于算法簡單理解，且為第一個被提出來的特性，常被算法教材拿來當作主定理（英語：Master theorem）計算時間復雜度的例子。

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

算法定義設A、B為域F上的方矩陣。求兩者的積{\displaystyle C}。一般矩陣可以填0的方法計算令它成為矩陣。

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

即

于是

引入新矩陣

可得：

其中的計算也是使用施特拉森算法求得。

評論一般矩陣乘法的時間復雜度為，施特拉森算法因為只有每次的分治法（英語：Divide and conquer algorithm）只有七個矩陣乘法運算，所以依照主定理（英語：Master theorem）可以得出時間復雜度為。但Strassen算法的數值穩(wěn)定性較差。

現時時間復雜度最低的矩陣乘法算法是Coppersmith-Winograd方法的一種擴展方法，其算法復雜度為)。1

本詞條內容貢獻者為:

程鵬 - 副教授 - 西南大學