Matrix Multiplication

$$c_{ij}=\sum _{k=1}^n{a}_{ik}{b}_{kj}$$

Algorithms

for i = 1 to n
    for j = 1 to n
        for k = 1 to n
            C[i, j] = A[i, k] * B[k, j]

This algorithm runs at $\Theta (n^3)$.

• Simple Divide and Conquer
  • Dividing each matrices into four $n/2\times n/2$ sub-matrices. Eight multiplications and four additions in total.
  • Partition methods: copying or index calculation.
  • This also runs at $\Theta (n^3)$, as the recursion-tree is “bushier”.
• Strassen’s algorithm for matrix multiplication.