Strassen Algorithm
Introduction
Given the two matrices of size
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
where
The master theorem states that
- If
for some constant , then . - If
, then . - If
for some constant , and if for some constant and all sufficiently large N, then .
Naive Algorithm
Matrix Multiplication
Suppose we have square matrices
Divide-And-Conquer
The divide-and-conquer approach could be applied to the matrix multiplication algorithm. Concretely,
and
To compute
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
The divide-and-conquer could be further applied to the submatrix multiplication, so that the asympotic complexity
We will use the master theorem to analyze the asymptotic complexity of this recursive algorithm.
Because
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,
and the matrix multiplication is computed using the following formula,
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
Similarly, we will use the master theorem to analyze the asymptotic complexity of this recursive algorithm.
Because
This suggests that the divide-and-conquer for the Strassen algorithm will improve the asymptotic complexity of matrix multiplication from
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
References
Strassen Algorithm