主題
Search

Strassen 公式

下載 Mathematica 筆記本下載 Wolfram 筆記本

執行 n×n 矩陣乘法 通常所需的標量運算數（即，加法和乘法的總數）是

M(n)=2n^3-n^2
(1)

（即，n^3 次乘法和 n^3-n^2 次加法）。然而，Strassen (1969) 發現瞭如何用

S(n)=7·7^(lgn)-6·4^(lgn)
(2)

次標量運算來乘兩個 矩陣，其中 lg 是以 2 為底的 對數，這小於 M(n)，當 n>654 時。對於 n 為 2 的冪次方 (n=2^k)，(2) 的兩部分可以寫成

7·7^(lgn)=7·7^(lg2^k)
(3)
=7·7^k
(4)
=7·2^(klg7)
(5)
=7(2^k)^(lg7)
(6)
=7n^(lg7)
(7)
6·4^(lgn)=6·4^(lg2^k)
(8)
=6·4^(klg2)
(9)
=6·4^k
(10)
=6(2^k)^2
(11)
=6n^2,
(12)

因此 (◇) 變為

S(2^k)=7n^(lg7)-6n^2.
(13)

對於 2 的冪次方，Strassen 演算法的領先指數因此為 lg7 approx 2.808。

下表總結了 Coppersmith 和 Winograd (1990) 的構造在 m 次冪的領先指數 omega 中已證明的極限的改進（參見 Le Gall 2014，表 I）。

m上限參考文獻
12.3871900Coppersmith 和 Winograd (1990)
22.3754770Coppersmith 和 Winograd (1990)
42.3736898Strothers (2010), Davie 和 Strothers (2013)
42.3729269Vassilevska Williams (2012)
82.3729Vassilevska Williams (2014)
82.3728642Le Gall (2014)
162.3728640Le Gall (2014)
322.3728639Le Gall (2014)

使用 Strassen 乘法，2×2 矩陣可以相乘

C=AB
(14)
[c_(11) c_(12); c_(21) c_(22)]=[a_(11) a_(12); a_(21) a_(22)][b_(11) b_(12); b_(21) b_(22)]
(15)

僅需

S(2)=7·2^(lg7)-6·2^2=49-24=25
(16)

次標量運算（結果表明，其中七次是乘法，18 次是加法）。定義七個乘積（總共涉及 10 次加法）為

Q_1=(a_(11)+a_(22))(b_(11)+b_(22))
(17)
Q_2=(a_(21)+a_(22))b_(11)
(18)
Q_3=a_(11)(b_(12)-b_(22))
(19)
Q_4=a_(22)(-b_(11)+b_(21))
(20)
Q_5=(a_(11)+a_(12))b_(22)
(21)
Q_6=(-a_(11)+a_(21))(b_(11)+b_(12))
(22)
Q_7=(a_(12)-a_(22))(b_(21)+b_(22)).
(23)

然後，使用剩餘的八次加法，矩陣乘積給出為

c_(11)=Q_1+Q_4-Q_5+Q_7
(24)
c_(21)=Q_2+Q_4
(25)
c_(12)=Q_3+Q_5
(26)
c_(22)=Q_1+Q_3-Q_2+Q_6
(27)

（Strassen 1969, Press et al. 1989）。

一個 2×2 矩陣 A 的矩陣求逆以產生 C=A^(-1) 也可以用比預期更少的操作完成，使用以下公式

R_1=a_(11)^(-1)
(28)
R_2=a_(21)R_1
(29)
R_3=R_1a_(12)
(30)
R_4=a_(21)R_3
(31)
R_5=R_4-a_(22)
(32)
R_6=R_5^(-1)
(33)
c_(12)=R_3R_6
(34)
c_(21)=R_6R_2
(35)
R_7=R_3c_(21)
(36)
c_(11)=R_1-R_7
(37)
c_(22)=-R_6
(38)

（Strassen 1969, Press et al. 1989）。

不幸的是，Strassen 演算法的數值表現不佳。它只是弱穩定，即，計算結果 C=AB 滿足不等式

||C-AB||<=nu||A||||B||+O(u^2),
(39)

其中 u 是單位舍入誤差，而相應的強穩定性不等式（透過用矩陣元素的絕對值替換矩陣範數獲得）不成立。

另請參閱

複數乘法, Karatsuba 乘法

使用 探索

參考文獻

Coppersmith, D. 和 Winograd, S. "Matrix Multiplication via Arithmetic Programming." J. Symb. Comput. 9, 251-280, 1990.Davie, A. M.; 和 Strothers, A. J. "Improved Bound for Complexity of Matrix Multiplication." Proc. Royal Soc. Edinburgh 143A, 351-370, 2013.Douglas, C.; Heroux, M.; Slishman, G.; 和 Smith, R. "GEMMW: A Portable Level 3 BLAS Winograd Variant of Strassen's Matrix-Matrix Multiply Algorithm." J. Comput. Phys. 110, 1-10, 1994.Le Gall, F. "Powers of Tensors and Fast Matrix Multiplication." 2014 年 1 月 30 日. https://arxiv.org/abs/1401.7714.Pan, V. How to Multiply Matrices Faster. New York: Springer-Verlag, 1982.Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; 和 Vetterling, W. T. "Is Matrix Inversion an N^3 Process?" §2.11 in Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England: Cambridge University Press, pp. 95-98, 1989.Strassen, V. "Gaussian Elimination is Not Optimal." Numerische Mathematik 13, 354-356, 1969.Strothers, A. "On the Complexity of Matrix Multiplication." Ph.D. 論文. Edinburgh, Scottland: University of Edinburgh, 2010.Vassilevska Williams, V. "Multiplying Matrices Faster Than Coppersmith-Winograd." In STOC'12--Proceedings of the 2012 ACM Symposium on Theory of Computing. New York: ACM, pp. 887-898, 2012.Vassilevska Williams, V. "Multiplying Matrices in O(n^2.373)." 2014 年 7 月 1 日. http://theory.stanford.edu/~virgi/matrixmult-f.pdf.

在 上被引用

Strassen 公式

請引用為

Weisstein, Eric W. "Strassen 公式。" 來自 --一個 資源。 https://mathworld.tw/StrassenFormulas.html

主題分類