Strassen Algorithm.md

행렬의 곱셈

$n \times n$ 행렬 $A, B$에 대해 $C$를 $A$와 $B$의 곱이라고 한다면 $C$의 임의의 원소 $c_{ij}$는 $\sum_{k=1}^n a_{ik} \cdot b_{kj}$로 나타낼 수 있다.

기계적으로 행렬의 곱셈을 계산한다면, $c_{ij}$를 계산할 때 k 값을 1부터 n까지 전부 확인하고, 원소가 총 $n^2$개이므로 이 방식의 시간복잡도는 $\Theta(n^3)$이다.

1편: 분할 정복

$A=\begin{pmatrix} A_{11} & A_{12} \ A_{21} & A_{22} \end{pmatrix}$, $B=\begin{pmatrix} B_{11} & B_{12} \ B_{21} & B_{22} \end{pmatrix}$, $C=\begin{pmatrix} C_{11} & C_{12} \ C_{21} & B_{22} \end{pmatrix}$로 분할한다고 할 때,

$\begin{pmatrix} C_{11} & C_{12} \ C_{21} & B_{22} \end{pmatrix}=\begin{pmatrix} A_{11} & A_{12} \ A_{21} & A_{22} \end{pmatrix} \cdot\begin{pmatrix} B_{11} & B_{12} \ B_{21} & B_{22} \end{pmatrix}$ 가 되고, C의 분할들을 계산하면... $C_{11}=A_{11} \cdot B_{11} + A_{12} \cdot B_{21}$,

$C_{12}=A_{11} \cdot B_{12} + A_{12} \cdot B_{22}$,

$C_{21}=A_{21} \cdot B_{11} + A_{22} \cdot B_{21}$,

$C_{22}=A_{21} \cdot B_{12} + A_{22} \cdot B_{22}$

가 된다. 각 과정마다 분할된 집합의 곱을 구하는 과정이 2번씩 들어가고, 이 과정을 4번씩 반복한다. 또한, 이들을 더하는 데 드는 시간 복잡도가 $\Theta(n^2)$이므로 이 과정의 경우, 시간복잡도가 $T(n)=8T(n/2)+\Theta(n^2)$가 되고, 이 식을 풀어 보면... $T(n)=\Theta(n^3)$이다.

이 방법 그대로는 사용할 수 없고, 아이디어만 차용해서 분할의 횟수를 줄여야 한다.

2편: 스트라센 알고리즘

일차적으로 이하와 같이 분할한다. $S_1=B_{12}-B_{22}$

$S_2=A_{11}-A_{12}$

$S_3=A_{21}+A_{22}$

$S_4=B_{21}-B_{11}$

$S_5=A_{11}+A_{22}$

$S_6=B_{11}+B_{22}$

$S_7=A_{12}-A_{22}$

$S_8=B_{21}+B_{22}$

$S_9=A_{11}-A_{21}$

$S_{10}=B_{11}+B_{12}$

그 이후, 이들을 통해 이하와 같은 배열들을 추가로 제작한다.

$P_1=A_{11} \cdot S_1=A_{11}\cdot B_{12}-A_{11} \cdot B_{22}$

$P_2=S_2 \cdot B_{22}=A_{11}\cdot B_{22}+A_{12} \cdot B_{22}$

$P_3=S_3 \cdot B_{1}=A_{21}\cdot B_{11}+A_{22} \cdot B_{11}$

$P_4=A_{22} \cdot S_4=A_{22}\cdot B_{21}-A_{22} \cdot B_{11}$

$P_5=S_5 \cdot S_6=A_{11}\cdot B_{11}+A_{11} \cdot B_{22}+A_{22} \cdot B_{11}+A_{22} \cdot B_{22}$

$P_6=S_7 \cdot S_8=A_{12}\cdot B_{21}+A_{12} \cdot B_{22}-A_{22} \cdot B_{21}-A_{22} \cdot B_{22}$

$P_7=S_9 \cdot S_10=A_{11}\cdot B_{11}+A_{11} \cdot B_{12}-A_{21} \cdot B_{11}-A_{21} \cdot B_{12}$

이후, C를 쪼개 얻은 4개의 배열을 다시 표기하면...

$C_{11}=P_5+P_4-P_2+P_6$

$C_{12}=P_1+P_2$

$C_{21}=P_3+P_4$

$C_{22}=P_5+P_1-P_3-P_7$

P의 개수가 7개이므로, 여기서는 시간이 $T(n)=7T(n/2)+\Theta(n^2)$가 되고, 식을 풀면 $T(n)=\Theta(n^{lg7})$이 된다.