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