施特拉森演算法

施特拉森演算法（）是一個計算矩陣乘法的演算法，時間複雜度為。

 簡介 
400px|thumb|right|矩陣乘法演算法的演進。

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

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

 算法 
 定義 
設、為域上的方矩陣。求兩者的積。一般矩陣可以填0的方法計算令它成為矩陣。

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

即

於是

引入新矩陣

可得：

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

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

現時時間複雜度最低的矩陣乘法演算法是Coppersmith-Winograd方法的一种扩展方法，其算法复杂度为)。而1990年Coppersmith-Winograd方法提出时的算法复杂度为。

 相關連結 
 矩陣乘法

 参考来源 

Category:数值线性代数
Category:算法