슈트라센 알고리즘

선형대수학에서 **슈트라센 알고리즘**은 독일의 수학자 폴커 슈트라센(Volker Strassen)이 1969년에 개발한 행렬 곱셈 알고리즘이다. 정의에 따라 *n*×*n* 크기의 두 행렬을 곱하면 O(n3)의 시간이 소요되지만 이 알고리즘은 대략 O(n2.81)의 시간이 소요된다.
# 알고리즘
*A*와 *B*를 체 *F*에 대한 정사각행렬이라고 하자. 두 행렬의 곱 *C*는 다음과 같다. : \mathbf{C} = \mathbf{A} \mathbf{B} \qquad \mathbf{A},\mathbf{B},\mathbf{C} \in F^{2^n \times 2^n} 만약 *A*와 *B*가 2n × 2n 꼴의 크기가 아니라면 먼저 모자라는 행과 열을 0으로 채운다. 이 경우 행렬 곱셈이 끝난 뒤 행렬에서 필요한 부분만 다시 잘라 내야 한다. 이제 *A*, *B*, *C*를 같은 크기의 정사각행렬 네 개로 나눈다. : \mathbf{A} = \begin{bmatrix} \mathbf{A}_{1,1} & \mathbf{A}_{1,2} \\\ \mathbf{A}_{2,1} & \mathbf{A}_{2,2} \end{bmatrix} \mbox { , } \mathbf{B} = \begin{bmatrix} \mathbf{B}_{1,1} & \mathbf{B}_{1,2} \\\ \mathbf{B}_{2,1} & \mathbf{B}_{2,2} \end{bmatrix} \mbox { , } \mathbf{C} = \begin{bmatrix} \mathbf{C}_{1,1} & \mathbf{C}_{1,2} \\\ \mathbf{C}_{2,1} & \mathbf{C}_{2,2} \end{bmatrix} 이 때, :\mathbf{A}_{i,j}, \mathbf{B}_{i,j}, \mathbf{C}_{i,j} \in F^{2^{n-1} \times 2^{n-1 따라서 다음이 성립한다. :\mathbf{C}_{1,1} = \mathbf{A}_{1,1} \mathbf{B}_{1,1} + \mathbf{A}_{1,2} \mathbf{B}_{2,1} :\mathbf{C}_{1,2} = \mathbf{A}_{1,1} \mathbf{B}_{1,2} + \mathbf{A}_{1,2} \mathbf{B}_{2,2} :\mathbf{C}_{2,1} = \mathbf{A}_{2,1} \mathbf{B}_{1,1} + \mathbf{A}_{2,2} \mathbf{B}_{2,1} :\mathbf{C}_{2,2} = \mathbf{A}_{2,1} \mathbf{B}_{1,2} + \mathbf{A}_{2,2} \mathbf{B}_{2,2} 이 과정에서는 필요한 연산의 수가 줄어 들지 않는다. 여전히 *Ci,j* 행렬을 계산하려면 여덟 번의 곱셈과 네 번의 덧셈이 필요하다. 이제 다음과 같은 행렬을 정의한다. :\mathbf{M}_{1} := (\mathbf{A}_{1,1} + \mathbf{A}_{2,2}) (\mathbf{B}_{1,1} + \mathbf{B}_{2,2}) :\mathbf{M}_{2} := (\mathbf{A}_{2,1} + \mathbf{A}_{2,2}) \mathbf{B}_{1,1} :\mathbf{M}_{3} := \mathbf{A}_{1,1} (\mathbf{B}_{1,2} - \mathbf{B}_{2,2}) :\mathbf{M}_{4} := \mathbf{A}_{2,2} (\mathbf{B}_{2,1} - \mathbf{B}_{1,1}) :\mathbf{M}_{5} := (\mathbf{A}_{1,1} + \mathbf{A}_{1,2}) \mathbf{B}_{2,2} :\mathbf{M}_{6} := (\mathbf{A}_{2,1} - \mathbf{A}_{1,1}) (\mathbf{B}_{1,1} + \mathbf{B}_{1,2}) :\mathbf{M}_{7} := (\mathbf{A}_{1,2} - \mathbf{A}_{2,2}) (\mathbf{B}_{2,1} + \mathbf{B}_{2,2}) 이 *Mk* 행렬들은 *Ci,j* 행렬을 표현하는 데 쓰이는데, 이 행렬들을 계산하는 데는 일곱 번의 곱셈(각 변수마다 한 번씩)과 10번의 덧셈이 필요하다. 이제 *Ci,j* 행렬은 다음과 같이 표현할 수 있다. :\mathbf{C}_{1,1} = \mathbf{M}_{1} + \mathbf{M}_{4} - \mathbf{M}_{5} + \mathbf{M}_{7} :\mathbf{C}_{1,2} = \mathbf{M}_{3} + \mathbf{M}_{5} :\mathbf{C}_{2,1} = \mathbf{M}_{2} + \mathbf{M}_{4} :\mathbf{C}_{2,2} = \mathbf{M}_{1} - \mathbf{M}_{2} + \mathbf{M}_{3} + \mathbf{M}_{6} 이 과정에서는 곱셈이 사용되지 않기 때문에, 전체 곱셈을 일곱 번의 곱셈과 18번의 덧셈으로 처리할 수 있다. 큰 행렬에 대해서는 행렬의 곱셈이 덧셈보다 더 많은 시간을 필요로 하기 때문에 덧셈을 더 하는 대신 곱셈을 덜 하는 것이 전체적으로 더 효율적이다. 이 과정을 재귀적으로 반복할 경우 총 7 \cdot n^{\log_2 7} - 6 \cdot n^2번의 연산이 필요하다. \log_2 7 = 2.807\cdots이므로 전체 수행 시간은 약 O(n2.807)이다. 실제로는 *n*이 작을 경우 정의에 따라 행렬 곱셈을 하는 경우가 빠를 수도 있기 때문에, 보통 작은 *n*에 대해서는 일반적인 방법으로 곱셈을 하도록 구현한다. 슈트라센 알고리즘은 속도에 비해 수치 안정성이 떨어지는 것으로 알려져 있다. 두 행렬 *A*와 *B*를 곱한 결과를 *C*라 할 때, 실제 오차인 \lVert C-AB \rVert는 27 n^2 u \lVert A \rVert \lVert B \rVert + O(u^2)보다 작음이 알려져 있다. 이는 일반적인 행렬 곱셈보다 더 큰 오차이다.Paolo D'Alberto, Alexandru Nicolau, "Adaptive Strassen and ATLAS’s DGEMM: A Fast Square-Matrix Multiply for Modern High-Performance Systems," *hpcasia*, pp. 45-52, Eighth International Conference on High-Performance Computing in Asia-Pacific Region (HPCASIA'05), 2005.
# 변형된 알고리즘
슈무엘 위노그라드(Shmuel Winograd)는 1980년에 슈트라센 알고리즘을 변형한 **위노그라드 알고리즘**(Winograd algorithm)을 개발하였다. 이 알고리즘은 점근적으로 슈트라센 알고리즘과 동일한 복잡도를 지니지만 덧셈의 횟수를 15번으로 줄인 방법이다. 이 방법에서는 다음과 같은 변수를 쓴다. :{| cellpadding="3" width="60%" | \mathbf{S}_1 = \mathbf{A}_{21} + \mathbf{A}_{22} || \mathbf{S}_2 = \mathbf{S}_1 - \mathbf{A}_{11} |- | \mathbf{S}_3 = \mathbf{B}_{12} - \mathbf{B}_{11} || \mathbf{S}_4 = \mathbf{B}_{22} - \mathbf{S}_3 |- | \mathbf{M}_1 = \mathbf{S}_2 \mathbf{S}_4 || \mathbf{M}_2 = \mathbf{A}_{11} \mathbf{B}_{11} |- | \mathbf{M}_3 = \mathbf{A}_{12} \mathbf{B}_{21} || \mathbf{M}_4 = (\mathbf{A}_{11} - \mathbf{A}_{21}) (\mathbf{B}_{22} - \mathbf{B}_{12}) |- | \mathbf{M}_5 = \mathbf{S}_1 \mathbf{S}_3 || \mathbf{M}_6 = (\mathbf{A}_{12} - \mathbf{S}_2) \mathbf{B}_{22} |- | \mathbf{M}_7 = \mathbf{A}_{22} (\mathbf{S}_4 - \mathbf{B}_{21}) |- | \mathbf{T}_1 = \mathbf{M}_1 + \mathbf{M}_2 || \mathbf{T}_2 = \mathbf{T}_1 + \mathbf{M}_4 |} 이 때 행렬 곱셈의 결과는 다음과 같이 주어진다. :\mathbf{C}_{11} = \mathbf{M}_2 + \mathbf{M}_3 :\mathbf{C}_{12} = \mathbf{T}_1 + \mathbf{M}_5 + \mathbf{M}_6 :\mathbf{C}_{21} = \mathbf{T}_2 - \mathbf{M}_7 :\mathbf{C}_{22} = \mathbf{T}_2 + \mathbf{M}_5 빅터 판(Victor Pan)은 슈트라센 알고리즘에서 행렬을 더 잘게 나눠서 O(n2.795)의 시간 안에 행렬을 곱하는 방법을 개발했다. 그는 68×68 행렬은 132,464번의 곱셈으로, 70×70 행렬은 143,640번의 곱셈으로, 72×72 행렬은 155,424번의 곱셈으로 계산이 가능함을 보였다. 돈 코퍼스미스(Don Coppersmith)와 슈무엘 위노그라드는 1987년에 또 다른 알고리즘인 **코퍼스미스-위노그라드 알고리즘**(Coppersmith–Winograd algorithm)을 개발했다. 이 알고리즘 역시 슈트라센 알고리즘처럼 재귀적 발상에서 나온 것으로, 시간 복잡도가 O(n2.376)이고 2010년에 Stother가 O(n2.3737)로 개선할 때까지 가장 빠른 알고리즘이었다. 이듬해 월리엄스가 O(n2.3727)로 개선한 알고리즘이 현존하는 가장 빠른 알고리즘이다. 2005년에는 이 알고리즘을 군론적 구성을 사용해 유도한 논문이 발표되었다.
# 참고 자료
* Strassen, Volker, *Gaussian Elimination is not Optimal*, Numer. Math. 13, p. 354-356, 1969 * Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. *Introduction to Algorithms*, Second Edition. MIT Press and McGraw-Hill, 2001. . Chapter 28: Section 28.2: Strassen's algorithm for matrix multiplication, pp.735–741. * Henry Cohn, Robert Kleinberg, Balazs Szegedy, and Chris Umans. Group-theoretic Algorithms for Matrix Multiplication. *Proceedings of the 46th Annual Symposium on Foundations of Computer Science*, 23-25 October 2005, Pittsburgh, PA, IEEE Computer Society, pp. 379–388. * Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. *Journal of Symbolic Computation*, 9:251–280, 1990.