施特拉森演算法 (英語: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))
矩陣 。
C
=
A
B
A
,
B
,
C
∈
F
2
n
×
2
n
{\displaystyle \mathbf {C} =\mathbf {A} \mathbf {B} \qquad \mathbf {A} ,\mathbf {B} ,\mathbf {C} \in F^{2^{n}\times 2^{n))}
將A , B , C 分成相等大小的方塊矩陣:
A
=
[
A
1
,
1
A
1
,
2
A
2
,
1
A
2
,
2
]
,
B
=
[
B
1
,
1
B
1
,
2
B
2
,
1
B
2
,
2
]
,
C
=
[
C
1
,
1
C
1
,
2
C
2
,
1
C
2
,
2
]
{\displaystyle \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))}
即
A
i
,
j
,
B
i
,
j
,
C
i
,
j
∈
F
2
n
−
1
×
2
n
−
1
{\displaystyle \mathbf {A} _{i,j},\mathbf {B} _{i,j},\mathbf {C} _{i,j}\in F^{2^{n-1}\times 2^{n-1))}
於是
C
1
,
1
=
A
1
,
1
B
1
,
1
+
A
1
,
2
B
2
,
1
{\displaystyle \mathbf {C} _{1,1}=\mathbf {A} _{1,1}\mathbf {B} _{1,1}+\mathbf {A} _{1,2}\mathbf {B} _{2,1))
C
1
,
2
=
A
1
,
1
B
1
,
2
+
A
1
,
2
B
2
,
2
{\displaystyle \mathbf {C} _{1,2}=\mathbf {A} _{1,1}\mathbf {B} _{1,2}+\mathbf {A} _{1,2}\mathbf {B} _{2,2))
C
2
,
1
=
A
2
,
1
B
1
,
1
+
A
2
,
2
B
2
,
1
{\displaystyle \mathbf {C} _{2,1}=\mathbf {A} _{2,1}\mathbf {B} _{1,1}+\mathbf {A} _{2,2}\mathbf {B} _{2,1))
C
2
,
2
=
A
2
,
1
B
1
,
2
+
A
2
,
2
B
2
,
2
{\displaystyle \mathbf {C} _{2,2}=\mathbf {A} _{2,1}\mathbf {B} _{1,2}+\mathbf {A} _{2,2}\mathbf {B} _{2,2))
引入新矩陣
M
1
:=
(
A
1
,
1
+
A
2
,
2
)
(
B
1
,
1
+
B
2
,
2
)
{\displaystyle \mathbf {M} _{1}:=(\mathbf {A} _{1,1}+\mathbf {A} _{2,2})(\mathbf {B} _{1,1}+\mathbf {B} _{2,2})}
M
2
:=
(
A
2
,
1
+
A
2
,
2
)
B
1
,
1
{\displaystyle \mathbf {M} _{2}:=(\mathbf {A} _{2,1}+\mathbf {A} _{2,2})\mathbf {B} _{1,1))
M
3
:=
A
1
,
1
(
B
1
,
2
−
B
2
,
2
)
{\displaystyle \mathbf {M} _{3}:=\mathbf {A} _{1,1}(\mathbf {B} _{1,2}-\mathbf {B} _{2,2})}
M
4
:=
A
2
,
2
(
B
2
,
1
−
B
1
,
1
)
{\displaystyle \mathbf {M} _{4}:=\mathbf {A} _{2,2}(\mathbf {B} _{2,1}-\mathbf {B} _{1,1})}
M
5
:=
(
A
1
,
1
+
A
1
,
2
)
B
2
,
2
{\displaystyle \mathbf {M} _{5}:=(\mathbf {A} _{1,1}+\mathbf {A} _{1,2})\mathbf {B} _{2,2))
M
6
:=
(
A
2
,
1
−
A
1
,
1
)
(
B
1
,
1
+
B
1
,
2
)
{\displaystyle \mathbf {M} _{6}:=(\mathbf {A} _{2,1}-\mathbf {A} _{1,1})(\mathbf {B} _{1,1}+\mathbf {B} _{1,2})}
M
7
:=
(
A
1
,
2
−
A
2
,
2
)
(
B
2
,
1
+
B
2
,
2
)
{\displaystyle \mathbf {M} _{7}:=(\mathbf {A} _{1,2}-\mathbf {A} _{2,2})(\mathbf {B} _{2,1}+\mathbf {B} _{2,2})}
可得:
C
1
,
1
=
M
1
+
M
4
−
M
5
+
M
7
{\displaystyle \mathbf {C} _{1,1}=\mathbf {M} _{1}+\mathbf {M} _{4}-\mathbf {M} _{5}+\mathbf {M} _{7))
C
1
,
2
=
M
3
+
M
5
{\displaystyle \mathbf {C} _{1,2}=\mathbf {M} _{3}+\mathbf {M} _{5))
C
2
,
1
=
M
2
+
M
4
{\displaystyle \mathbf {C} _{2,1}=\mathbf {M} _{2}+\mathbf {M} _{4))
C
2
,
2
=
M
1
−
M
2
+
M
3
+
M
6
{\displaystyle \mathbf {C} _{2,2}=\mathbf {M} _{1}-\mathbf {M} _{2}+\mathbf {M} _{3}+\mathbf {M} _{6))
其中
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]