4a. Matrix Multiplication

One of the Applications of Divide and Conquer

Algorithmic Perspective

Problem: given two matrices $X,Y$ output $Z=X\cdot Y$

$$Z_{ij}=\sum _{k=1}^n{X}_{ik}{Y}_{kj}$$

Running time: compute each $Z_{ij}$ takes $O(n)$. There are $n^2$ entries of $Z$ for a total of $O(n^3)$ time. Lower-bound running time: $O(n^2)$.

Assume $n$ is a power of 2. Let A, B, C, D, E, F, G, H be $n/2$ size matrices.

$$X=\left(\begin{array}{cc}A& B\\ C& D\end{array}\right)$$ $$Y=\left(\begin{array}{cc}E& F\\ G& H\end{array}\right)$$ $$Z=XY=\left(\begin{array}{cc}AE+BG& AF+BH\\ CE+DE& CF+DH\end{array}\right)$$

This demonstrates a recursive Divide and Conquer algorithm, calling 8 subproblems of size $n/2$. Recombination time: $O(n^2)$

• Why does it have an $O(n^2)$ recombination time?

Recurrence for matrix multiplication: $T(n)=8T(n/3)+O(n^2)=O(n^3)$ Same as a naive algorithm. Can we do 2x2 matrix multiplication with fewer than 8 multiplications?

Strassen’s Algorithm

Each $P_i$ involves 1 matrix multiplication, so we used 7 matrix multiplications (less than 8). Running time: $T(n)=7T(n/2)+O(n^2)$

• bottom layer dominates
• $T(n)=O(lo{g}_{2}7)\approx n^{2.81}$
• faster than $n^3$
• best known algorithm
• not employed often because sparse matrices have different effects on runtime
• big open problem: is $O(n^2)$ possible or impossible?