Statement

Let $p \in {\mbox{${\mathbb{N}}$}}$ and $n = 2^p$ . Let $A$ and $B$ be two square matrices of order $n$ and with coefficients in ${\mathbb{Z}}$ . The classical algorithm for computing the matrix product $A \, B$ uses ${\cal O}(n^3)$ operations in ${\mathbb{Z}}$ . The Strassen algorithm provides the lower asymptotic upper bound ${\cal O}(n^{2,81})$ . As for the Karatsuba algorithm, the trick relies on a smart use of distributivity:

$(1)$

If $n=1$ the matrices $A$ et $B$ are of the form $(a)$ et $(b)$ where $a, b \in {\mbox{${\mathbb{Z}}$}}$ , such that $A \, B$ equals $(a \, b)$ .

$(2)$

If $n > 1$ the matrices $A$ and $B$ can be decomposed as

$$A = \left( \begin{array}{cc} A_{11} & A_{12} \\ A_{21} & A... ...}{cc} B_{11} & B_{12} \\ B_{21} & B_{22} \end{array}\right),$$

where $A_{ij}$ and $B_{ij}$ are square matrices of order $n/2$ . Then, one computes the following 8 sums.

$$\begin{array}{ll} S_1 = A_{21} + A_{22} \ \ \ \ & T_1 = B_{1... ...S_4 = A_{12} - S_2 \ \ \ \ & T_4 = T_2 - B_{21} \\ \end{array}$$

$(3)$

Next, one computes the following 7 matrix products by recursive calls to the algorithm.

$$\begin{array}{ll} P_1 = A_{11} \, B_{11} \ \ \ \ & P_5 = S_1... ... \ & P_7 = S_3 \, T_3 \\ P_4 = A_{22} \, T_4 & \\ \end{array}$$

$(4)$

Finally, one computes the following 7 sums:

$$\begin{array}{ll} U_1 = P_1 + P_2 \ \ \ \ & U_5 = U_4 + P_3 ... ...\ \ \ \ & U_7 = U_3 + P_5 \\ U_4 = U_2 + P_5 & \\ \end{array}$$

and one returns:

$$\left( \begin{array}{cc} U_1 & U_5 \\ U_6 & U_7 \\ \end{array}\right).$$