施特拉森演算法（）是一個計算矩陣乘法的演算法，時間複雜度為O(n^{\log_2 7}) = O(n^{2.807})。
簡介
施特拉森演算法在1969年由沃爾克·施特拉森所提出，是第一個時間複雜度低於O(n^3)的矩陣乘法演算法。由於演算法簡單理解，且為第一個被提出來的特性，常被演算法教材拿來當作主定理（）計算時間複雜度的例子。
另外，因為施特拉森演算法證明了矩陣乘法存在時間複雜度低於O(n^3)的演算法，使得更多學者投入研究，尋找更快的演算法。
算法
定義
設A、B為域F上的方矩陣。求兩者的積C。一般矩陣可以填0的方法計算令它成為2^n \times 2^n矩陣。
:\mathbf{C} = \mathbf{A} \mathbf{B} \qquad \mathbf{A},\mathbf{B},\mathbf{C} \in F^{2^n \times 2^n}
計算
將A, B, C分成相等大小的方塊矩陣：
:
\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}
即
:\mathbf{A}_{i,j}, \mathbf{B}_{i,j}, \mathbf{C}_{i,j} \in F^{2^{n-1} \times 2^{n-1}}
於是
:\mathbf{C}_{1,1} = \mathbf{A}_{1,1} \mathbf{B}_{1,1} + \mathbf{A}_{1,2} \mathbf{B}_{2,1}
:\mathbf{C}_{1,2} = \mathbf{A}_{1,1} \mathbf{B}_{1,2} + \mathbf{A}_{1,2} \mathbf{B}_{2,2}
:\mathbf{C}_{2,1} = \mathbf{A}_{2,1} \mathbf{B}_{1,1} + \mathbf{A}_{2,2} \mathbf{B}_{2,1}
:\mathbf{C}_{2,2} = \mathbf{A}_{2,1} \mathbf{B}_{1,2} + \mathbf{A}_{2,2} \mathbf{B}_{2,2}
引入新矩陣
:\mathbf{M}_{1} := (\mathbf{A}_{1,1} + \mathbf{A}_{2,2}) (\mathbf{B}_{1,1} + \mathbf{B}_{2,2})
:\mathbf{M}_{2} := (\mathbf{A}_{2,1} + \mathbf{A}_{2,2}) \mathbf{B}_{1,1}
:\mathbf{M}_{3} := \mathbf{A}_{1,1} (\mathbf{B}_{1,2} - \mathbf{B}_{2,2})
:\mathbf{M}_{4} := \mathbf{A}_{2,2} (\mathbf{B}_{2,1} - \mathbf{B}_{1,1})
:\mathbf{M}_{5} := (\mathbf{A}_{1,1} + \mathbf{A}_{1,2}) \mathbf{B}_{2,2}
:\mathbf{M}_{6} := (\mathbf{A}_{2,1} - \mathbf{A}_{1,1}) (\mathbf{B}_{1,1} + \mathbf{B}_{1,2})
:\mathbf{M}_{7} := (\mathbf{A}_{1,2} - \mathbf{A}_{2,2}) (\mathbf{B}_{2,1} + \mathbf{B}_{2,2})
可得：
:\mathbf{C}_{1,1} = \mathbf{M}_{1} + \mathbf{M}_{4} - \mathbf{M}_{5} + \mathbf{M}_{7}
:\mathbf{C}_{1,2} = \mathbf{M}_{3} + \mathbf{M}_{5}
:\mathbf{C}_{2,1} = \mathbf{M}_{2} + \mathbf{M}_{4}
:\mathbf{C}_{2,2} = \mathbf{M}_{1} - \mathbf{M}_{2} + \mathbf{M}_{3} + \mathbf{M}_{6}
其中M_{i,j}的計算也是使用施特拉森演算法求得。
評論
一般矩陣乘法的時間複雜度為O(n^{\log_28}) = O(n^3)，施特拉森演算法因為只有每次的分治法（）只有七個矩陣乘法運算，所以依照主定理（）可以得出時間複雜度為O(n^{\log_27}) = O(n^{2.807})。但Strassen演算法的數值穩定性較差。
現時時間複雜度最低的矩陣乘法演算法是Coppersmith-Winograd方法的一种扩展方法，其算法复杂度为O(n^{2.3727})。
相關連結
- 矩陣乘法
参考来源
评论 (0)