슈트라센 알고리즘

$N*N$ 행렬 2개를 서로 곱하는 것을 생각해보자. 두 행렬을 곱해도 행렬의 크기는 $N*N$ 일 것이고, 각각의 칸은 $N$ 번의 곱셈을 통해 값을 산출할 수 있으니 총 $N^3$ 번의 곱셈으로 행렬을 곱할 수 있다. 나쁘지 않아 보이지만 이 방법이 최선의 시간복잡도를 가지는 것은 아니다. 이 글에서는 행렬 곱의 시간복잡도를 낮춘 슈트라센 알고리즘을 소개하고자 한다.

먼저 $N$ 을 2의 거듭제곱수로 가정하자. 그리고 행렬 $A, B, C$ 를 전부 $N*N$ 크기의 $A*B=C$ 를 만족하는 행렬들이라고 하자. $A, B, C$ 를 각각 정사각 부분행렬로 나타내면

\[A = \begin{Bmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{Bmatrix} \qquad B = \begin{Bmatrix} B_{11} & B_{12} \\ B_{21} & B_{22} \end{Bmatrix} \qquad C = \begin{Bmatrix} C_{11} & C_{12} \\ C_{21} & C_{22} \end{Bmatrix}\]

로 나타낼 수 있고, 각각의 부분행렬은 $N/2*N/2$ 의 크기를 가질 것이다. 여기서 $C$ 를 계산하기 위해 그의 부분행렬들을 구하는 방법을 사용하도록 하자. 그러면

\[ C_{11} = A_{11}B_{11} + A_{12}B_{21} \qquad C_{12} = A_{11}B_{12} + A_{12}B_{22} \\ C_{21} = A_{21}B_{11} + A_{22}B_{21} \qquad C_{22} = A_{21}B_{12} + A_{22}B_{22} \]

이렇게 $C$ 의 부분행렬들을 구할 수 있다. 하지만 이렇게만 한다면 시간복잡도는 전혀 개선되지 않을 것이다. 여전히 $C$ 를 구하려면 8번의 곱셈과 4번의 덧셈이 필요하다. 이제 여기에 새로운 행렬들을 정의할 것이다.

\[ 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}) \]

이 행렬들을 구하는 데에는 7번의 곱셈과 10번의 덧셈이 필요하다. 그리고 이 행렬들을 이용해서 $C$ 의 부분행렬들을 구할 수 있다.

\[ 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 \]

이 과정에는 총 8번의 덧셈이 필요하고, $C$ 의 모든 부분행렬을 구하는 데에는 7번의 곱셈과 18번의 덧셈이 필요하다. 정의에 따른 기존의 방식에 비해 1번의 곱셈을 덜 하는 대신 14번의 추가적인 덧셈을 하게 되었다. 하지만 덧셈보다 곱셈에 소요되는 시간복잡도가 훨씬 크기 때문에 점근 표기법으로 표현하는 시간복잡도는 오히려 줄어들게 된다.

마지막으로 슈트라센 알고리즘의 시간복잡도를 구해보도록 하자. 이 알고리즘은 재귀적이니 Master Theorem에 따라 연산 횟수를 구해보면 총 $7N^{\log_2{7}}-6N^2$ 번을 하고, 점근 표기법으로 나타낸다면 $O(N^{\log_2{7}}) = O(N^{2.807})$ 으로 기존의 $O(N^3)$ 보다 획기적으로 개선되었다. 물론 이것이 최선의 알고리즘은 아니며 현재도 최선의 알고리즘을 찾기 위해 부단한 노력을 하고 있지만, 행렬 곱을 개선하려는 첫 시도를 성공시켰으며 충분한 실용성도 갖췄다는 점에서 이 알고리즘이 가지는 의의는 결코 작지 않다고 할 수 있다.