# Strassen's Algorithm for matrix multiplication

Can someone demonstrate the multiplication of two $4\times 4$ matrices using Strassen's algorithm? I don't understand when to stop partitioning the matrices.

We first partition the two $4\times 4$ matrices into four $2\times 2$ submatrices. Is that where we stop? Or do we have to apply the same procedure recursively to the submatrices as well?

Thanks!

• You should show how the algorithm works exactly, or at least give a link. – Peter Aug 18 '15 at 13:20
• @peter Strassen's algorithm is well-known, and the many people who can answer this question will not need the reminder. – MJD Aug 18 '15 at 13:22
• Short answer is that yes, the procedure applies "recursively" to multiplying the seven pairs of $2\times 2$ matrices. That's where the improvement over $O(n^3)$ complexity comes from. A longer answer would hinge on just how much you need to be demonstrated to you. Or was this an assignment you were given to carry out? – hardmath Aug 18 '15 at 13:26
• @hardmath It isn't an assignment given to me. I'm just trying to understand how does the algorithm really work. Most of the sources simply give away the general algorithm. I could not find any examples. And, will there not be 8 pairs of $2\times 2$ matrices? – Neha Aug 18 '15 at 13:34
• @hardmath So,basically we keep partitioning the matrices until we are left with just numbers i.e $1\times 1$ matrices? A worked out example will help me understand the algorithm and thereafter, I can try understanding the analysis. Although I have read the analysis of the algorithm and to some extent have been able to get a brief idea of what's happening. – Neha Aug 18 '15 at 14:07

In the general case we would recursively divide each $n\times n$ matrix into four $\lceil n/2 \rceil \times \lceil n/2 \rceil$ matrices, adjoining a extra row and column of zeros if $n$ is odd to make the sizes of submatrices whole numbers.

The point here is that Strassen's formulas for multiplying a pair of $2\times 2$ matrices does not assume commutativity of the multiplication on the underlying entries (though it does assume multiplication distributes over addition and the usual properties of addition). It is therefore valid even when the "entries" of the $2\times 2$ matrices are themselves block submatrices.

The simplest case to illustrate this is multiplication of two $4\times 4$ matrices:

$$\begin{pmatrix} A & B \\ C & D \end{pmatrix} \begin{pmatrix} E & F \\ G & H \end{pmatrix}$$

where $A,B,C,D,E,F,G,H$ are each $2\times 2$ submatrices.

Strassen's algorithm can then be applied recursively. At the top level we want to form these seven products of $2\times 2$ matrices:

\begin{align*} M_1 &= (A+D)(E+H) \\ M_2 &= (C+D)E \\ M_3 &= A(F-H) \\ M_4 &= D(G-E) \\ M_5 &= (A+B)H \\ M_6 &= (C-A)(E+F) \\ M_7 &= (B-D)(G+H) \end{align*}

From these the top-level product can be expressed:

$$\begin{pmatrix} M_1 + M_4 - M_5 + M_7 & M_3 + M_5 \\ M_2 + M_4 & M_1 - M_2 + M_3 + M_6 \end{pmatrix}$$

The interested Reader should verify for themselves that when $A$ through $H$ are scalars, the result agrees with the usual row and column operations. The only thing one needs for the general proof is careful checking that no multiplication of the individual entries is assumed to commute when verifying that agreement.

For simplicity let's check just that the upper right corner gives $AF+BH$:

\begin{align*} M_3 + M_5 &= A(F-H) + (A+B)H \\ &= (AF - AH) + (AH + BH) \\ &= AF + BH \end{align*}

It follows that the formulas are valid in particular when $A$ through $H$ are the $2\times 2$ matrices defined above.