Strassen Formulas

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The usual number of scalar operations (i.e., the total number of additions and multiplications) required to perform n×n matrix multiplication is

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

(1)

(i.e., n^3 multiplications and n^3-n^2 additions). However, Strassen (1969) discovered how to multiply two matrices in

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

(2)

scalar operations, where lg is the logarithm to base 2, which is less than M(n) for n>654. For n a power of two (n=2^k), the two parts of (2) can be written

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)

so (◇) becomes

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

(13)

The leading exponent for Strassen's algorithm for a power of 2 is therefore lg7 approx 2.808.

The folowing table summarizes the improvements of proven limits in the leading exponent omega for mth powers of the construction of Coppersmith and Winograd (1990) over time (cf. Le Gall 2014, Table I).

m upper bound reference

1 2.3871900 Coppersmith and Winograd (1990)

2 2.3754770 Coppersmith and Winograd (1990)

4 2.3736898 Strothers (2010), Davie and Strothers (2013)

4 2.3729269 Vassilevska Williams (2012)

8 2.3729 Vassilevska Williams (2014)

8 2.3728642 Le Gall (2014)

16 2.3728640 Le Gall (2014)

32 2.3728639 Le Gall (2014)

Using Strassen multipication, 2×2 matrices can be multiplied

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)

with only

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

(16)

scalar operations (as it turns out, seven of them are multiplications and 18 are additions). Define the seven products (involving a total of 10 additions) as

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)

Then the matrix product is given using the remaining eight additions as

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).

Matrix inversion of a 2×2 matrix A to yield C=A^(-1) can also be done in fewer operations than expected using the formulas

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).

Unfortunately, Strassen's algorithm is not numerically well-behaved. It is only weakly stable, i.e., the computed result C=AB satisfies the inequality

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

(39)

where u is the unit roundoff error, while the corresponding strong stability inequality (obtained by replacing matrix norms with absolute values of the matrix elements) does not hold.

AlphaTensor, a reinforcement-learning system developed by DeepMind, found a method for multiplying 4×4 matrices over Z_2 using 47 scalar multiplications. This improves on the 49 multiplications obtained by applying Strassen's formulas twice (Fawzi et al. 2022).

Explore with Wolfram|Alpha

WolframAlpha

More things to try:

References

Coppersmith, D. and Winograd, S. "Matrix Multiplication via Arithmetic Programming." J. Symb. Comput. 9, 251-280, 1990.Davie, A. M.; and Strothers, A. J. "Improved Bound for Complexity of Matrix Multiplication." Proc. Royal Soc. Edinburgh 143A, 351-370, 2013.Douglas, C.; Heroux, M.; Slishman, G.; and Smith, R. "GEMMW: A Portable Level 3 BLAS Winograd Variant of Strassen's Matrix-Matrix Multiply Algorithm." J. Comput. Phys. 110, 1-10, 1994.Fawzi, A. et al. "Discovering Faster Matrix Multiplication Algorithms With Reinforcement Learning." Nature 610, 47-53, 2022. https://doi.org/10.1038/s41586-022-05172-4.Le Gall, F. "Powers of Tensors and Fast Matrix Multiplication." 30 Jan 2014. 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.; and 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. thesis. Edinburgh, Scotland: 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)." Jul. 1, 2014. http://theory.stanford.edu/~virgi/matrixmult-f.pdf.

Referenced on Wolfram|Alpha

Strassen Formulas

Cite this as:

Weisstein, Eric W. "Strassen Formulas." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/StrassenFormulas.html

Strassen Formulas

See also

Explore with Wolfram|Alpha

References

Referenced on Wolfram|Alpha

Cite this as:

Subject classifications