TOPICS
Search

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

mupper boundreference
12.3871900Coppersmith and Winograd (1990)
22.3754770Coppersmith and Winograd (1990)
42.3736898Strothers (2010), Davie and Strothers (2013)
42.3729269Vassilevska Williams (2012)
82.3729Vassilevska Williams (2014)
82.3728642Le Gall (2014)
162.3728640Le Gall (2014)
322.3728639Le 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.

See also

Complex Multiplication, Karatsuba Multiplication

Explore with Wolfram|Alpha

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.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, 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)." 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 Web Resource. https://mathworld.wolfram.com/StrassenFormulas.html

Subject classifications