쉬트라센 알고리즘 (Strassen Algorithm)

1960년대 후반 Strassen이 $O(n^3)$보다 작은 알고리즘을 제시하며 아래와 같은 규칙을 사용한다.

 

$P = (A_{11} + A_{22})(B_{11} + B_{22})$

$Q = (A_{21} + A_{22})B_{11}$ 
$R = A_{11}(B_{12}-B_{22})$ 
$S = A_{22}(B_{21}-B_{11})$ 
$T = (A_{11}+A_{12})B_{22}$ 
$U = (A_{21}-A_{11})(B_{11}+B_{12})$
$V = (A_{12}-A_{22})(B_{21}+B_{22})$

 

위의 규칙에서 사용되는 P~V까지를 통해, 덧셈만으로 A 행렬과 B 행렬의 곱인 C 행렬을 찾을 수 있다.

 

$C_{11} = P + S - T + V$ 
$C_{12} = R + T$ 
$C_{21} = Q + S$ 
$C_{22} = P + R -Q +U$

 

구체적으로 다시 설명을 하면 다음과 같다.

 

아래와 같이 행렬 A,B가 있고 두 행렬의 곱이 행렬 C로 표현한다 가정한다.

 

$A = \left[ \begin{array}{cc|c} a_{11} & a_{12} \\\\ a_{21} & a_{22} \end{array} \right],\ $ $B= \left[ \begin{array}{cc|c} b_{11} & b_{12} \\\\ b_{21} & b_{22} \end{array} \right],\ $ $C=\left[ \begin{array}{cc|c} c_{11} & c_{12} \\\\ c_{21} & c_{22} \end{array} \right]$

 

이 때, $A_{ij},B_{ij},C_{ij} \in F^{2^n-1 \times 2^n-1}$ 이다.

 

따라서 일반적인 행렬의 곱은 다음과 같이 표현할 수 있으며, 총 8번의 곱셈과 4번의 덧셈으로 연산된다.

 

$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}$

 

슈트라센 알고리즘은 행렬의 곱셉을 더하기 연산으로 풀어 각 원소를 구할 수 있는 $M$이라는 연산 행렬로 표현한다. 행렬 $M$은 7번의 곱셈과 10번의 덧셈으로 연산으로 나타낼 수 있으며 아래와 같이 표현한다.

 

$M_1 = (A_{11} + A_{22})(B_{11}+B_{22})$ 
$M_2 = (A_{21} + A_{22})B_{11}$ 
$M_3 = A_{11} (B_{12}-B_{22})$ 
$M_4 = A_{22}(B_{21}-B_{11})$ 
$M_5 = (A_{11} + A_{12})B_{22}$ 
$M_6 = (A_{21} - A_{11})(B_{11}+B_{12})$ 
$M_7 = (A_{12} - A_{22})(B_{21}+B_{22})$

 

최종적으로 행렬 C는 행렬 M의 더하기 연산으로 이루어져 있으며 각 원소에 해당하는 방법은 다음과 같다.

 

$C_{11} = M_1 + M_4 - M_5 + M_7$ 
$C_{12} = M_3 + M_5$ 
$C_{21} = M_2 + M_4$ 
$C_{22} = M_1 - M_2 + M_3 + M_6$

 

Reference

---

[1] https://loveisaround.tistory.com/entry/알고리즘-스트라센-strassen

[2] https://09ri.tistory.com/30