施特拉森演算法(英語:Strassen algorithm)是一個計算矩陣乘法的演算法,時間複雜度為 O ( n log 2 7 ) = O ( n 2.807 ) {\displaystyle O(n^{\log _{2}7})=O(n^{2.807})} 。
施特拉森演算法在1969年由沃爾克·施特拉森所提出,是第一個時間複雜度低於 O ( n 3 ) {\displaystyle O(n^{3})} 的矩陣乘法演算法。由於演算法簡單理解,且為第一個被提出來的特性,常被演算法教材拿來當作主定理(英語:Master theorem)計算時間複雜度的例子。
另外,因為施特拉森演算法證明了矩陣乘法存在時間複雜度低於 O ( n 3 ) {\displaystyle O(n^{3})} 的演算法,使得更多學者投入研究,尋找更快的演算法。
設 A {\displaystyle A} 、 B {\displaystyle B} 為域 F {\displaystyle F} 上的方矩陣。求兩者的積 C {\displaystyle C} 。一般矩陣可以填0的方法計算令它成為 2 n × 2 n {\displaystyle 2^{n}\times 2^{n}} 矩陣。
將A, B, C分成相等大小的方塊矩陣:
即
於是
引入新矩陣
可得:
其中 M i , j {\displaystyle M_{i,j}} 的計算也是使用施特拉森演算法求得。
一般矩陣乘法的時間複雜度為 O ( n log 2 8 ) = O ( n 3 ) {\displaystyle O(n^{\log _{2}8})=O(n^{3})} ,施特拉森演算法因為只有每次的分治法(英語:Divide and conquer algorithm)只有七個矩陣乘法運算,所以依照主定理(英語:Master theorem)可以得出時間複雜度為 O ( n log 2 7 ) = O ( n 2.807 ) {\displaystyle O(n^{\log _{2}7})=O(n^{2.807})} 。但Strassen演算法的數值穩定性較差。
現時時間複雜度最低的矩陣乘法演算法是Coppersmith-Winograd方法的一种扩展方法,其算法复杂度为 O ( n 2.3727 {\displaystyle O(n^{2.3727}} )。[1]