Conventional matrix multiplication

Let A and B be two n × n matrices. The product matrix C = AB is also an n × n matrix, whose (i, j)^th element is formed by taking the elements in the i^th row of A and the j^th column of B:

To compute C(i, j) we need n multiplications. Hence conventional matrix multiplication takes $\Theta \left(n^3\right)$ time.

Divide-and-conquer strategy

Let n be a power of 2, $n=2^k$. If n is not a power of 2, append enough rows and columns of zeros to both A and B, so that the resulting dimensions are a power of two.

Imagine A and B are partitioned into 4 square submatrices, each submatrix having dimension $\frac{n}{2}\times \frac{n}{2}$. Then the product AB of 2 × 2 matrices is:

then

Since n is a power of 2, these matrix products can be recursively computed by the same algorithm, until the submatrices become small with n = 2.

Cost of the plain divide-and-conquer method

To compute AB, we need 8 multiplications of $\frac{n}{2}\times \frac{n}{2}$ matrices and 4 additions of $\frac{n}{2}\times \frac{n}{2}$ matrices.

Here $c{n}^2$ is the addition time, and b and c are constants. This gives $T\left(n\right)=O\left(n^3\right)$. Hence there is no improvement over the traditional method.

Strassen's method

Strassen discovered a way to compute the C_ij's using 7 multiplications and 18 additions or subtractions.

Time complexity of Strassen's method

The resulting recurrence relation is:

Solution (short form)

Solution by repeated substitution

Let $n=2^k$, so $k={\log }_{2}n$:

∴ The time complexity is $O\left(n^{{\log }_{2}7}\right)$ or $O\left(n^{2.81}\right)$, which is better than the $O\left(n^3\right)$ of the conventional method.

In the derivation above, T(1) is taken as 1 and the constant factor from summing the geometric series is absorbed into c, as in the handwritten notes.