Overview

기존 행렬 곱셈은 $O(N^3)$이다. 그러나 Divide-and-Conquer를 활용하여 Time Complexity를 줄일 수 있다.

기존 행렬 곱셈

$\begin{Bmatrix}C_{11} & C_{12} \\C_{21} & C_{22}\end{Bmatrix} =\begin{Bmatrix}A_{11} & A_{12} \\A_{21} & A_{22}\end{Bmatrix}\begin{Bmatrix}B_{11} & B_{12} \\B_{21} & B_{22}\end{Bmatrix}$

• $C_{11} = A_{11}B_{11} + A_{12}B_{21}$
• $C_{12} = A_{11}B_{12} + A_{12}B_{22}$
• $C_{21} = A_{21}B_{11} + A_{22}B_{21}$
• $C_{22} = A_{21}B_{12} + A_{22}B_{22}$

총 8번의 곱셈이 진행된다. ($2^{log_2 8} = 2^3$)

코드로 확인

for i in range(N):
    for j in range(N):
        C[i][j]

여기서 $\begin{aligned} C_{ij} = \sum_{k=1}^N A_{ik} B_{kj} \end{aligned}$이므로,

$\begin{aligned} \therefore T(N)=\sum_{i=1}^N \sum_{j=1}^N \sum_{k=1}^N c = c N^3 = O(N^3) \end{aligned}$

Strassen’s 행렬 곱셈

Divide-and-Conquer를 활용한 방식이다.

• $C11 = P1 + P4 - P5 + P7$
• $C12 = P3 + P5$
• $C21 = P2 + P4$
• $C22 = P1 + P3 - P2 + P6$
• 곱셈 수식 정리