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

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

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

\begin{displaymath}
\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}\end{displaymath}

$ (3)$
Next, one computes the following 7 matrix products by recursive calls to the algorithm.

\begin{displaymath}
\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}\end{displaymath}

$ (4)$
Finally, one computes the following 7 sums:

\begin{displaymath}
\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}\end{displaymath}

and one returns:

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

Marc Moreno Maza
2008-03-18