22
$\begingroup$

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.

$\endgroup$

3 Answers 3

23
$\begingroup$

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.

$\endgroup$
14
$\begingroup$

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, other 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.

$\endgroup$
1
  • 4
    $\begingroup$ Such bases are called an M-pair, see the chapter on algebras of minimal rank in the book by Bürgisser, Clausen, and Shokrollahi. I think it is quite hard to come up with the idea that M-pairs exist without knowing the Alder-Strassen theorem (see again the book above). In particular, $2\times 2$-matrices are the only matrix algebra for which an M-pair exists. $\endgroup$ Commented Mar 27, 2013 at 8:09
4
$\begingroup$

Several authors have attempted to elucidate the structure of Strassen's algorithm. The two most recent I am aware of are:

  • Ikenmeyer and Lysikov '17 give a beautiful exposition, though ultimately the key is the same 4x4 multiplication table mentioned in Yuval Filmus's answer
  • Grochow and Moore '17 gave an alternative construction based on group orbits, that generalizes to a bound of $n^3-n+1$ for all $n$. Technically this gives different matrices than those that are given by Strassen, but by the De Groote result mentioned in Markus Bläser's answer, they are necessarily equivalent up to a change of basis.

Both papers provide further references for prior explanations of Strassen's algorithm.

The idea of the latter is that if you take $v_1, \dotsc, v_k$ that form an orbit of a group $G$ inside a non-trivial irreducible representation $V$ of $G$, then you can use the facts that $\sum v_i = 0$ and $\sum v_i^t v_i = \alpha I$ for some nonzero scalar $\alpha$ (both of which follow from the $v_i$ being an orbit in a nontrivial irrep) to quickly get a decomposition of the matrix multiplication tensor as

$I \otimes I \otimes I + \sum_{i,j,k \text{ distinct}} v_i^t (v_j - v_i) \otimes v_j^t(v_k - v_i) \otimes v_k^t (v_i - v_k)$.

The smallest such case happens for $G=S_3$ in its two-dimensional irrep, where the $v_i$ are the corners of an equilateral triangle. As the size of this orbit is 3, it gives the bound 1 (for the term $I^{\otimes 3}$) + 6 (there are six triples $(i,j,k)$ with $i,j,k \in \{1,2,3\}$ which index the summation in the formula above) = 7.

This presentation also makes manifest more of the symmetry between the terms that "appears"* to be lacking in Strassen's original presentation (as mentioned in the OQ). In terms of the $A$'s and $B$'s, here both the $A$'s and the $B$'s are $\{v_i^t (v_j - v_i) : i,j \text{ distinct}\} \cup \{I\}$. Somewhat interestingly, when viewed in this way, the $A$'s (resp., $B$'s) form a spanning set of 2x2 matrices which is strictly larger than a basis.

(Open question: the matrices in this construction only work in rings that have the constants $\sqrt{3}, 1/2, 1/3$, whereas Strassen's original construction only used integers, so it works in any ring. Is there a construction of Strassen's algorithm that has similar structure to this one, but only uses integers?)

* I say "appears to be lacking" because by De Groote's result, the symmetries are still there in Strassen's original presentation, they are just harder to see. The symmetries of Strassen's algorithm are discussed in great detail by Burichenko '14; there are even more than are visible from the above construction!)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.