施特拉森算法

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

基本介紹

• 中文名：施特拉森算法
• 外文名：Strassen algorithm

簡介

矩陣乘法算法的演進。

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

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

算法

定義

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

計算

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

即

於是

引入新矩陣

可得：

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

評論

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

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