Strassen Algorithm

Introduction

Given the two matrices of size $N \times N$, their matrix multiplication using the conventional definition takes $O(N^3)$ asymptotically. The Strassen algorithm is the first matrix multiplication algorithm that asymptotically does better than $O(N^3)$ developed by Volker Strassen in 1960s.

In this blog post, let’s quickly discuss the Strassen algorithm and analyze its asymptotic complexity using the master theorem.

Prerequisite

Master Theorem

The master theorem is useful for the asymptotic analysis for divide-and-conquer algorithms. It states that the runtime of the divide-and-conquer algorithm could usually be described as

$$
\begin{align}
T(N) &=
\begin{cases}
\Theta(1) & \text{if $N = 1$}\\
aT(\frac{N}{b}) + f(N) & \text{if $N > 1$}\\
\end{cases} \\
\end{align}
$$

where $a \geq 1$ and $b > 1$.

The master theorem states that

1. If $f(N) = O(N^{\log_{b} a - \epsilon})$ for some constant $\epsilon > 0$, then $T(N) = \Theta(N^{\log_{b} a})$.
2. If $f(N) = \Theta(N^{\log_{b} a})$, then $T(N) = \Theta(N^{\log_{b} a} \lg N)$.
3. If $f(N) = \Omega(N^{\log_{b} a + \epsilon})$ for some constant $\epsilon > 0$, and if $aT(\frac{N}{b}) \leq cf(N)$ for some constant $c < 1$ and all sufficiently large N, then $T(N) = \Theta(f(N))$.

Naive Algorithm

Matrix Multiplication

Suppose we have square matrices $\mathbf{A}, \mathbf{B}, \mathbf{C} \in \mathbb{R}^{N \times N}$ where $N = 2^n$, to compute $\mathbf{C} = \mathbf{A} \mathbf{B}$ using the matrix multiplication definition, the number of multiplications and the number of additions required are both $N^3$, that is to say the asymptotic complexity of computing matrix multiplication using the definition is $\Theta(N^3)$.

Divide-And-Conquer

The divide-and-conquer approach could be applied to the matrix multiplication algorithm. Concretely, $\mathbf{A}, \mathbf{B}, \mathbf{C}$ are partitioned into equal-sized blocked matrices so that

$$
\mathbf{A} =
\begin{bmatrix}
\mathbf{A}_{1,1} & \mathbf{A}_{1,2} \\
\mathbf{A}_{2,1} & \mathbf{A}_{2,2} \\
\end{bmatrix}
,\quad
\mathbf{B} =
\begin{bmatrix}
\mathbf{B}_{1,1} & \mathbf{B}_{1,2} \\
\mathbf{B}_{2,1} & \mathbf{B}_{2,2} \\
\end{bmatrix}
,\quad
\mathbf{C} =
\begin{bmatrix}
\mathbf{C}_{1,1} & \mathbf{C}_{1,2} \\
\mathbf{C}_{2,1} & \mathbf{C}_{2,2} \\
\end{bmatrix}
$$

and $\mathbf{A}_{i,j}, \mathbf{B}_{i,j}, \mathbf{C}_{i,j} \in \mathbb{R}^{\frac{N}{2} \times \frac{N}{2}}$.

To compute $\mathbf{C} = \mathbf{A} \mathbf{B}$,

$$
\begin{bmatrix}
\mathbf{C}_{1,1} & \mathbf{C}_{1,2} \\
\mathbf{C}_{2,1} & \mathbf{C}_{2,2} \\
\end{bmatrix}
=
\begin{bmatrix}
\mathbf{A}_{1,1} \mathbf{B}_{1,1} + \mathbf{A}_{1,2} \mathbf{B}_{2,1} & \mathbf{A}_{1,1} \mathbf{B}_{1,2} + \mathbf{A}_{1,2} \mathbf{B}_{2,2} \\
\mathbf{A}_{2,1} \mathbf{B}_{1,1} + \mathbf{A}_{2,2} \mathbf{B}_{2,1} & \mathbf{A}_{2,1} \mathbf{B}_{1,2} + \mathbf{A}_{2,2} \mathbf{B}_{2,2} \\
\end{bmatrix}
$$

The number of submatrix multiplications and the number of submatrix additions required for the above formula are both 8. Because the number of multiplications and additions for each submatrix multiplication are both $(\frac{N}{2})^3 = \frac{N^3}{8}$ and the number of additions for each submatrix addition is $(\frac{N}{2})^2 = \frac{N^2}{4}$,

The divide-and-conquer could be further applied to the submatrix multiplication, so that the asympotic complexity $T(N)$ follows

$$
\begin{align}
T(N) &=
\begin{cases}
\Theta(1) & \text{if $N = 1$}\\
8T(\frac{N}{2}) + \Theta(N^2) & \text{if $N > 1$}\\
\end{cases} \\
\end{align}
$$

We will use the master theorem to analyze the asymptotic complexity of this recursive algorithm.

Because $T(N) = aT(\frac{N}{b}) + f(N)$, $a = 8$, $b = 2$, $\log_{b} {a} = 3$, $\epsilon = 1$, $f(N) = O(N^{\log_{b} {a} - \epsilon})$, the master theorem tells us that $T(N) = \Theta(N^{\log_{b} {a}}) = \Theta(N^3)$.

This suggests that the divide-and-conquer for the native algorithm will not improve the asymptotic complexity of matrix multiplication.

Strassen Algorithm

Divide-And-Conquer

The Strassen algorithm is also a divide-and-conquer algorithm. It defines new matrices,

$$
\begin{align}
\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}_{2,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}) \\
\end{align}
$$

and the matrix multiplication is computed using the following formula,

$$
\begin{bmatrix}
\mathbf{C}_{1,1} & \mathbf{C}_{1,2} \\
\mathbf{C}_{2,1} & \mathbf{C}_{2,2} \\
\end{bmatrix}
=
\begin{bmatrix}
\mathbf{M}_{1} + \mathbf{M}_{4} - \mathbf{M}_{5} + \mathbf{M}_{7} & \mathbf{M}_{3} + \mathbf{M}_{5} \\
\mathbf{M}_{2} + \mathbf{M}_{4} & \mathbf{M}_{1} - \mathbf{M}_{2} + \mathbf{M}_{3} + \mathbf{M}_{6} \\
\end{bmatrix}
$$

The correctness of the algorithm can be easily verified.

The number of submatrix multiplications for the above formula becomes 7, and the number of submatrix additions for the above formula becomes 22.

The divide-and-conquer could be further applied to the submatrix multiplication, so that the asympotic complexity $T(N)$ follows

$$
\begin{align}
T(N) &=
\begin{cases}
\Theta(1) & \text{if $N = 1$}\\
7T(\frac{N}{2}) + \Theta(N^2) & \text{if $N > 1$}\\
\end{cases} \\
\end{align}
$$

Similarly, we will use the master theorem to analyze the asymptotic complexity of this recursive algorithm.

Because $T(N) = aT(\frac{N}{b}) + f(N)$, $a = 7$, $b = 2$, $\log_{b} {a} = 2.8074$, $\epsilon = 0.8074$, $f(N) = O(N^{\log_{b} {a} - \epsilon})$, the master theorem tells us that $T(N) = \Theta(N^{\log_{b} {a}}) = \Theta(N^{2.8074})$.

This suggests that the divide-and-conquer for the Strassen algorithm will improve the asymptotic complexity of matrix multiplication from $\Theta(N^3)$ to $\Theta(N^{2.8074})$.

Non-Square Matrix Multiplication

In fact, the Strassen algorithm can also deal with the multiplication of non-square matrices. For non-square matrices whose dimensions are still even, we can still partition the matrices $\mathbf{A}, \mathbf{B}, \mathbf{C}$ evenly into square matrices and it is easy to verify that the submatrix multiplications and additions in the Strassen algorithm are all valid. For dimension sizes that are odd, simply pad a row or a column filled with zeros so that the matrix dimension sizes become even.

References

• Strassen Algorithm
• Discovering Faster Matrix Multiplication Algorithms with Reinforcement Learning
• Master Theorem