60. Strassen's Algorithm

스트라센 알고리즘(Strassen's Algorithm)은 행렬 곱셈을 $\Theta(n^3)$보다 빠른 시간에 하는 알고리즘이며 카라츠바 알고리즘과 유사하게 분할 정복을 이용하여 시간복잡도를 줄인다. 크기가 $n \times n$인 두 행렬 $A$와 $B$가 존재하고, $A$와 $B$의 곱이 행렬 $C$일 때 스트라센 알고리즘의 작동 방식은 다음과 같다. 먼저 각 행렬을 $4$등분해서 다음과 같이 나눈다.

 

$$A = \begin{bmatrix} A_{1, 1} & A_{1, 2} \\ A_{2, 1} & A_{2, 2} \end{bmatrix}, B = \begin{bmatrix} B_{1, 1} & B_{1, 2} \\ B_{2, 1} & B_{2, 2} \end{bmatrix}, C = \begin{bmatrix} C_{1, 1} & C_{1, 2} \\ C_{2, 1} & C_{2, 2} \end{bmatrix}$$

 

이때 $C$의 각 부분을 $A$와 $B$의 각 부분들에 대해서 나타내면 다음과 같다.

$$C_{1, 1} = A_{1, 1} \times B_{1, 1} + A_{1, 2} \times B_{2, 1}$$

$$C_{1, 2} = A_{1, 1} \times B_{1, 2} + A_{1, 2} \times B_{2, 2}$$$$C_{2, 1} = A_{2, 1} \times B_{1, 1} + A_{2, 2} \times B_{2, 1}$$$$C_{2, 2} = A_{2, 1} \times B_{1, 2} + A_{2, 2} \times B_{2, 2}$$

 

이 식에는 크기가 $\frac{n}{2} \times \frac{n}{2}$인 행렬의 곱셈이 총 $8$번 등장하며, 겹치는 곱셈은 없다. 따라서 이렇게 나누는 것만으로는 시간복잡도가 줄어들지 않는다.

 

이제 $A$와 $B$의 부분 행렬들을 적절히 더하고 빼서 크기가 $\frac{n}{2} \times \frac{n}{2}$인 행렬 $10$개를 만든다. 각각의 행렬을 만드는 연산은 다음과 같다.

$$W_1 = A_{1, 1} + A_{1, 2}$$

$$W_2 = A_{1, 1} - A_{2, 1}$$

$$W_3 = A_{1, 1} + A_{2, 2}$$

$$W_4 = A_{1, 2} - A_{2, 2}$$

$$W_5 = A_{2, 1} + A_{2, 2}$$

$$W_6 = B_{1, 1} + B_{1, 2}$$

$$W_7 = B_{1, 1} + B_{2, 2}$$

$$W_8 = B_{1, 2} - B_{2, 2}$$

$$W_9 = B_{2, 1} - B_{1, 1}$$

$$W_{10} = B_{2, 1} + B_{2, 2}$$

 

다음으로 크기가 $\frac{n}{2} \times \frac{n}{2}$인 행렬 $18$개를 적절히 곱해서 크기가 $\frac{n}{2} \times \frac{n}{2}$인 행렬 $7$개를 더 만든다.

$$P_1 = A_{1, 1} \times W_8 = A_{1, 1} \times B_{1, 2} - A_{1, 1} \times B_{2, 2}$$

$$P_2 = W_1 \times B_{2, 2} = A_{1, 1} \times B_{2, 2} + A_{1, 2} \times B_{2, 2}$$

$$P_3 = W_5 \times B_{1, 1} = A_{2, 1} \times B_{1, 1} + A_{2, 2} \times B_{1, 1}$$

$$P_4 = A_{2, 2} \times W_9 = A_{2, 2} \times B_{2, 1} - A_{2, 2} \times B_{1, 1}$$

$$P_5 = W_2 \times W_6 = A_{1, 1} \times B_{1, 1} + A_{1, 1} \times B_{1, 2} - A_{2, 1} \times B_{1, 1} - A_{2, 1} \times B_{1, 2}$$

$$P_6 = W_3 \times W_7 = A_{1, 1} \times B_{1, 1} + A_{1, 1} \times B_{2, 2} + A_{2, 2} \times B_{1, 1} + A_{2, 2} \times B_{2, 2}$$

$$P_7 = W_4 \times W_{10} = A_{1, 2} \times B_{2, 1} + A_{1, 2} \times B_{2, 2} - A_{2, 2} \times B_{2, 1} - A_{2, 2} \times B_{2, 2}$$

 

이제 $C$의 부분 행렬은 이 행렬들을 이용하여 나타낼 수 있다.

$$C_{1, 1} = -P_2 + P_4 + P_6 + P_7$$

$$C_{1, 2} = P_1 + P_2$$

$$C_{2, 1} = P_3 + P_4$$

$$C_{2, 2} = P_1 - P_3 - P_5 + P_6$$

 

이제 크기가 $\frac{n}{2} \times \frac{n}{2}$인 행렬의 곱셈 $7$번으로 $A$와 $B$의 곱을 계산할 수 있으며 이를 재귀적으로 적용할 수 있다. 이 방법의 시간복잡도는 $\Theta(n^{\lg 7})$인데, 카라츠바 알고리즘과 마찬가지로 벡터 생성이 많아서 속도가 느리기 때문에 일반적인 $\Theta(n^3)$ 곱셈에 비해 속도가 개선되는 정도가 크지 않을 수 있다.