Skip to content

Strassen's Matrix Multiplication

Time Complexity of naive way of implementing this would be \(O(n^3)\).

Matrix Multiplication

For example, here [1, 2, 3, 4, 5, 6, 7], if 4 is chosen as a pivot element, it is also the median of the array. The array would be partitioned in two equal half for the next recursion.

\[\begin{bmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \\ \end{bmatrix}\]
\[\begin{bmatrix} b_{11} & b_{12} \\ b_{21} & b_{22} \\ \end{bmatrix}\]
\[\begin{bmatrix} c_{11} & c_{12} \\ c_{21} & c_{22} \\ \end{bmatrix}\]

\(A * B = C\)

\(c_{11} = a_{11}*b_{11} + a_{12}*b_{21}\)

Algorithm

func mm(A, B, n):
    if (n <= 2):
        perform normal matrix multiplication
    else:
        mid = n // 2
        mm(A11,B11,mid) + md(A12,B21,mid)
        mm(A11,B12,mid) + md(A12,B22,mid)
        mm(A21,B11,mid) + md(A22,B21,mid)
        mm(A21,B12,mid) + md(A22,B22,mid)

Time Complexity

This is recursive algorithm.

f(n) = \begin{cases} n/2, & \text{if \(n\) is even} \ 3n+1, & \text{if \(n\) is odd} \end{cases}

\left. \begin{array}{l} \text{if \(n\) is even:}&n/2\ \text{if \(n\) is odd:}&3n+1 \end{array} \right} =T(n)

$T(n) = 8*T(n/2) + n^2 $.

Time Complexity is \(\theta(n^3)\).

Strassen's Matrix M

Time Complexity is \(O(n^{2.81})\).