Bigger picture behind the choice of matrices in the Strassen algorithm

Question

In the Strassen algorithm, to compute the product of two matrices $\mathbf{A}$ and $\mathbf{B}$, the matrices $\mathbf{A}$ and $\mathbf{B}$ are divided into $2 \times 2$ block matrices and the algorithm proceeds recursively computing $7$ block matrix-matrix products as opposed to a naive $8$ block matrix-matrix products, i.e., if we want $\mathbf{C}=\mathbf{A} \mathbf{B}$, where $$\mathbf{A} =\begin{bmatrix} \mathbf{A}_{1,1} & \mathbf{A}_{1,2} \\ \mathbf{A}_{2,1} & \mathbf{A}_{2,2} \end{bmatrix} \mbox { , } \mathbf{B} = \begin{bmatrix} \mathbf{B}_{1,1} & \mathbf{B}_{1,2} \\ \mathbf{B}_{2,1} & \mathbf{B}_{2,2} \end{bmatrix} \mbox { , } \mathbf{C} = \begin{bmatrix} \mathbf{C}_{1,1} & \mathbf{C}_{1,2} \\ \mathbf{C}_{2,1} & \mathbf{C}_{2,2} \end{bmatrix}$$ then we have $$ \mathbf{C}_{1,1} = \mathbf{A}_{1,1} \mathbf{B}_{1,1} + \mathbf{A}_{1,2} \mathbf{B}_{2,1}\\ \mathbf{C}_{1,2} = \mathbf{A}_{1,1} \mathbf{B}_{1,2} + \mathbf{A}_{1,2} \mathbf{B}_{2,2}\\ \mathbf{C}_{2,1} = \mathbf{A}_{2,1} \mathbf{B}_{1,1} + \mathbf{A}_{2,2} \mathbf{B}_{2,1}\\ \mathbf{C}_{2,2} = \mathbf{A}_{2,1} \mathbf{B}_{1,2} + \mathbf{A}_{2,2} \mathbf{B}_{2,2} $$ which requires $8$ multiplications. Instead in Strassen, we compute $$ \mathbf{M}_{1} := (\mathbf{A}_{1,1} + \mathbf{A}_{2,2}) (\mathbf{B}_{1,1} + \mathbf{B}_{2,2})\\ \mathbf{M}_{2} := (\mathbf{A}_{2,1} + \mathbf{A}_{2,2}) \mathbf{B}_{1,1}\\ \mathbf{M}_{3} := \mathbf{A}_{1,1} (\mathbf{B}_{1,2} - \mathbf{B}_{2,2})\\ \mathbf{M}_{4} := \mathbf{A}_{2,2} (\mathbf{B}_{2,1} - \mathbf{B}_{1,1})\\ \mathbf{M}_{5} := (\mathbf{A}_{1,1} + \mathbf{A}_{1,2}) \mathbf{B}_{2,2}\\ \mathbf{M}_{6} := (\mathbf{A}_{2,1} - \mathbf{A}_{1,1}) (\mathbf{B}_{1,1} + \mathbf{B}_{1,2})\\ \mathbf{M}_{7} := (\mathbf{A}_{1,2} - \mathbf{A}_{2,2}) (\mathbf{B}_{2,1} + \mathbf{B}_{2,2}) $$ and obtain $\mathbf{C}_{i,j}$'s using $\mathbf{M}_{k}$'s as $$ \mathbf{C}_{1,1} = \mathbf{M}_{1} + \mathbf{M}_{4} - \mathbf{M}_{5} + \mathbf{M}_{7}\\ \mathbf{C}_{1,2} = \mathbf{M}_{3} + \mathbf{M}_{5}\\ \mathbf{C}_{2,1} = \mathbf{M}_{2} + \mathbf{M}_{4}\\ \mathbf{C}_{2,2} = \mathbf{M}_{1} - \mathbf{M}_{2} + \mathbf{M}_{3} + \mathbf{M}_{6} $$ However, the choice of the matrices $\mathbf{M}_k$'s seem arbitrary to me. Is there a bigger picture as to why we choose these specific products of sub-matrices of $\mathbf{A}$ and $\mathbf{B}$? Also, I would expect $\mathbf{M}_k$'s to involve $\mathbf{A}_{i,j}$'s and $\mathbf{B}_{i,j}$'s in a symmetric fashion, which does not seem to be the case here. For instance, we have $\mathbf{M}_2: = (\mathbf{A}_{2,1}+\mathbf{A}_{2,2})\mathbf{B}_{1,1}$. I would expect its counterpart say $\mathbf{A}_{1,1} (\mathbf{B}_{1,2} + \mathbf{B}_{2,2})$ also to be computed. However, it is not since it can be obtained from other $\mathbf{M}_k$'s.

I would appreciate if someone could throw some light on this.

Answer 1

De Groote (On Varieties of Optimal Algorithms for the Computation of Bilinear Mappings. II. Optimal Algorithms for 2x2-Matrix Multiplication. Theor. Comput. Sci. 7: 127-148, 1978) proves that there is only one algorithm to multiply $2 \times 2$-matrices with 7 multiplications up to equivalence. This might be a unique feature of $2 \times 2$-matrix multiplication. (Note: You will find different variants of Strassen's algorithm in the literature. They are all equivalent with the right notion of equivalence.)

If you now start to prove a lower bound for $2 \times 2$-matrix multiplication - see the book by Bürgisser, Clausen, and Shokrollahi how to do that - then Strassen's algorithm or some variant shows up quite naturally. You will find out a lot of identities that determine how the products look like. Then you can finish by some guessing. (De Groote's proof shows that even guessing is not necessary.)

Schönhage once told me that Strassen once told him that he found his algorithm in this way, by trying to prove a lower bound.

Answer 2

There is some sort of explanation in the book Algebraic Complexity Theory by Bürgisser, Clausen and Shokrollahi (p. 11-12). The idea is to start with two bases $A_0,A_1,A_2,A_3$ and $B_0,B_1,B_2,B_3$ of the space of $2\times 2$ real matrices which satisfy the following property: $A_iB_j \in \{0,A_0,A_1,A_2,A_3,B_0,B_1,B_2,B_3\}$. Furthermore, $A_0 = B_0$. To multiply two matrices $A$ and $B$, represent each of them in the corresponding basis, and evaluate the product. Since only seven different non-zero matrices appear in the result ($A_0=B_0,A_1,A_2,A_3,B_1,B_2,B_3$), only seven products are needed. The $M$ matrices are just these bases.

I don't know whether Strassen came up with this way of looking at it. Considering other identities underlying fast matrix multiplication algorithms, it's not clear whether there's anything deep going on, under than some formula working out. We've been through that before - Lagrange used the four square identity (which had been known before) to prove the four square theorem. At first it must have been just a curious algebraic identity, but now we know that it states the multiplicativity property of quaternion norm. Given the current state of knowledge, it is hard to tell whether the above interpretation is as productive.