CS 3343/3341
Analysis of Algorithms
  2-by-2 Matrix Produce   
with Seven Multiplications  


Strassen's Method.

Your textbook presents Strassen's Method for getting the product of two 2-by-2 matrices using 7 multiplications and 18 additions and subtractions. The text presents this by trying to show how the equations were discovered, but in the end it's hard to extract the formulas from their presentation. This page gives the formulas in a simple way using the text's notation.

The first formulas below show the product of two matrices. To carry out the matrix product in this way takes 8 multiplications and 4 additions.

The formulas in the next box show Strassen's method for computing the same 4 final values using only 7 multiplications and 18 additions and subtractions. (Notation the same as in your text.)

Finally, the next set of formulas give Winograd's improvement on Strassen's result, to get the 4 final values in 7 multiplications and 15 additions and subtractions (3 fewer than Strassen).

The number of addions and subtractions is not important as long as they are O(n2), since the asymptotic behavior is the same, although the implied constant is different.


Revision date: 2012-09-27. (Please use ISO 8601, the International Standard.)