查看“︁施特拉森演算法”︁的源代码

{{onesource|time=2014-09-03T20:55:35+00:00}}
'''施特拉森演算法'''（{{lang-en|Strassen algorithm}}）是一個計算[[矩陣乘法]]的[[演算法]]，時間複雜度為<math>O(n^{\log_2 7}) = O(n^{2.807})</math>。

== 簡介 ==
[[Image:Bound on matrix multiplication omega over time.svg|400px|thumb|right|矩陣乘法演算法的演進。]]

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

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

== 算法 ==
=== 定義 ===
設<math>A</math>、<math>B</math>為[[体 (数学)|域]]<math>F</math>上的方[[矩陣]]。求兩者的積<math>C</math>。一般矩陣可以填0的方法計算令它成為<math>2^n \times 2^n</math>[[矩陣]]。

:<math>\mathbf{C} = \mathbf{A} \mathbf{B} \qquad \mathbf{A},\mathbf{B},\mathbf{C} \in F^{2^n \times 2^n}</math>

=== 計算 ===
將''A'', ''B'', ''C''分成相等大小的方塊矩陣：
:<math> 
\mathbf{A} =
\begin{bmatrix}
\mathbf{A}_{1,1} & \mathbf{A}_{1,2} \\
\mathbf{A}_{2,1} & \mathbf{A}_{2,2}
\end{bmatrix}
\mbox { , }
\mathbf{B} =
\begin{bmatrix}
\mathbf{B}_{1,1} & \mathbf{B}_{1,2} \\
\mathbf{B}_{2,1} & \mathbf{B}_{2,2}
\end{bmatrix}
\mbox { , }
\mathbf{C} =
\begin{bmatrix}
\mathbf{C}_{1,1} & \mathbf{C}_{1,2} \\
\mathbf{C}_{2,1} & \mathbf{C}_{2,2}
\end{bmatrix}
</math>

即

:<math>\mathbf{A}_{i,j}, \mathbf{B}_{i,j}, \mathbf{C}_{i,j} \in F^{2^{n-1} \times 2^{n-1}}</math>

於是

:<math>\mathbf{C}_{1,1} = \mathbf{A}_{1,1} \mathbf{B}_{1,1} + \mathbf{A}_{1,2} \mathbf{B}_{2,1} </math>
:<math>\mathbf{C}_{1,2} = \mathbf{A}_{1,1} \mathbf{B}_{1,2} + \mathbf{A}_{1,2} \mathbf{B}_{2,2} </math>
:<math>\mathbf{C}_{2,1} = \mathbf{A}_{2,1} \mathbf{B}_{1,1} + \mathbf{A}_{2,2} \mathbf{B}_{2,1} </math>
:<math>\mathbf{C}_{2,2} = \mathbf{A}_{2,1} \mathbf{B}_{1,2} + \mathbf{A}_{2,2} \mathbf{B}_{2,2} </math>

引入新矩陣

:<math>\mathbf{M}_{1} := (\mathbf{A}_{1,1} + \mathbf{A}_{2,2}) (\mathbf{B}_{1,1} + \mathbf{B}_{2,2})</math>
:<math>\mathbf{M}_{2} := (\mathbf{A}_{2,1} + \mathbf{A}_{2,2}) \mathbf{B}_{1,1}</math>
:<math>\mathbf{M}_{3} := \mathbf{A}_{1,1} (\mathbf{B}_{1,2} - \mathbf{B}_{2,2})</math>
:<math>\mathbf{M}_{4} := \mathbf{A}_{2,2} (\mathbf{B}_{2,1} - \mathbf{B}_{1,1})</math>
:<math>\mathbf{M}_{5} := (\mathbf{A}_{1,1} + \mathbf{A}_{1,2}) \mathbf{B}_{2,2}</math>
:<math>\mathbf{M}_{6} := (\mathbf{A}_{2,1} - \mathbf{A}_{1,1}) (\mathbf{B}_{1,1} + \mathbf{B}_{1,2})</math>
:<math>\mathbf{M}_{7} := (\mathbf{A}_{1,2} - \mathbf{A}_{2,2}) (\mathbf{B}_{2,1} + \mathbf{B}_{2,2})</math>

可得：

:<math>\mathbf{C}_{1,1} = \mathbf{M}_{1} + \mathbf{M}_{4} - \mathbf{M}_{5} + \mathbf{M}_{7}</math>
:<math>\mathbf{C}_{1,2} = \mathbf{M}_{3} + \mathbf{M}_{5}</math>
:<math>\mathbf{C}_{2,1} = \mathbf{M}_{2} + \mathbf{M}_{4}</math>
:<math>\mathbf{C}_{2,2} = \mathbf{M}_{1} - \mathbf{M}_{2} + \mathbf{M}_{3} + \mathbf{M}_{6}</math>

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

== 評論 ==
一般矩陣乘法的時間複雜度為<math>O(n^{\log_28}) = O(n^3)</math>，施特拉森演算法因為只有每次的[[分治法]]（{{lang-en|Divide and conquer algorithm}}）只有七個矩陣乘法運算，所以依照[[主定理]]（{{lang-en|Master theorem}}）可以得出時間複雜度為<math>O(n^{\log_27}) = O(n^{2.807})</math>。但Strassen演算法的[[數值穩定性]]較差。

現時時間複雜度最低的矩陣乘法演算法是[[Coppersmith-Winograd方法]]的一种扩展方法，其算法复杂度为<math>O(n^{2.3727}</math>)。<ref>{{cite web|url=http://www.cs.stanford.edu/~virgi/matrixmult-f.pdf|title=Multiplying matrices faster than Coppersmith-Winograd|author=Virginia Vassilevska Williams|access-date=2014-01-14|archive-date=2013-10-08|archive-url=https://web.archive.org/web/20131008063524/http://www.cs.stanford.edu/~virgi/matrixmult-f.pdf|dead-url=no}}而1990年[[Coppersmith-Winograd方法]]提出时的算法复杂度为<math>O(n^{2.3727})</math>。</ref>

== 相關連結 ==
* [[矩陣乘法]]

== 参考来源 ==
{{Reflist}}

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