슈트라센 알고리즘 문서 원본 보기

{{위키데이터 속성 추적}}
[[선형대수학]]에서 '''슈트라센 알고리즘'''은 독일의 수학자 [[폴커 슈트라센]](Volker Strassen)이 [[1969년]]에 개발한 [[행렬 곱셈]] [[알고리즘]]이다. 정의에 따라 ''n''×''n'' 크기의 두 행렬을 곱하면 [[점근 표기법|O]](n<sup>3</sup>)의 시간이 소요되지만 이 알고리즘은 대략 O(n<sup>2.81</sup>)의 시간이 소요된다.

== 알고리즘 ==

''A''와 ''B''를 [[체 (수학)|체]] ''F''에 대한 [[행렬#정사각행렬|정사각행렬]]이라고 하자. 두 행렬의 곱 ''C''는 다음과 같다.
: <math>\mathbf{C} = \mathbf{A} \mathbf{B} \qquad \mathbf{A},\mathbf{B},\mathbf{C} \in F^{2^n \times 2^n}</math>

만약 ''A''와 ''B''가 2<sup>n</sup> × 2<sup>n</sup> 꼴의 크기가 아니라면 먼저 모자라는 행과 열을 0으로 채운다. 이 경우 행렬 곱셈이 끝난 뒤 행렬에서 필요한 부분만 다시 잘라 내야 한다.

이제 ''A'', ''B'', ''C''를 같은 크기의 정사각행렬 네 개로 나눈다.
:<math>
\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}
</math>

이 때,
:<math>\mathbf{A}_{i,j}, \mathbf{B}_{i,j}, \mathbf{C}_{i,j} \in F^{2^{n-1} \times 2^{n-1}}</math>

따라서 다음이 성립한다.
:<math>\mathbf{C}_{1,1} = \mathbf{A}_{1,1} \mathbf{B}_{1,1} + \mathbf{A}_{1,2} \mathbf{B}_{2,1} </math>
:<math>\mathbf{C}_{1,2} = \mathbf{A}_{1,1} \mathbf{B}_{1,2} + \mathbf{A}_{1,2} \mathbf{B}_{2,2} </math>
:<math>\mathbf{C}_{2,1} = \mathbf{A}_{2,1} \mathbf{B}_{1,1} + \mathbf{A}_{2,2} \mathbf{B}_{2,1} </math>
:<math>\mathbf{C}_{2,2} = \mathbf{A}_{2,1} \mathbf{B}_{1,2} + \mathbf{A}_{2,2} \mathbf{B}_{2,2} </math>

이 과정에서는 필요한 연산의 수가 줄어 들지 않는다. 여전히 ''C<sub>i,j</sub>'' 행렬을 계산하려면 여덟 번의 곱셈과 네 번의 덧셈이 필요하다.

이제 다음과 같은 행렬을 정의한다.
:<math>\mathbf{M}_{1} := (\mathbf{A}_{1,1} + \mathbf{A}_{2,2}) (\mathbf{B}_{1,1} + \mathbf{B}_{2,2})</math>
:<math>\mathbf{M}_{2} := (\mathbf{A}_{2,1} + \mathbf{A}_{2,2}) \mathbf{B}_{1,1}</math>
:<math>\mathbf{M}_{3} := \mathbf{A}_{1,1} (\mathbf{B}_{1,2} - \mathbf{B}_{2,2})</math>
:<math>\mathbf{M}_{4} := \mathbf{A}_{2,2} (\mathbf{B}_{2,1} - \mathbf{B}_{1,1})</math>
:<math>\mathbf{M}_{5} := (\mathbf{A}_{1,1} + \mathbf{A}_{1,2}) \mathbf{B}_{2,2}</math>
:<math>\mathbf{M}_{6} := (\mathbf{A}_{2,1} - \mathbf{A}_{1,1}) (\mathbf{B}_{1,1} + \mathbf{B}_{1,2})</math>
:<math>\mathbf{M}_{7} := (\mathbf{A}_{1,2} - \mathbf{A}_{2,2}) (\mathbf{B}_{2,1} + \mathbf{B}_{2,2})</math>

이 ''M<sub>k</sub>'' 행렬들은 ''C<sub>i,j</sub>'' 행렬을 표현하는 데 쓰이는데, 이 행렬들을 계산하는 데는 일곱 번의 곱셈(각 변수마다 한 번씩)과 10번의 덧셈이 필요하다. 이제 ''C<sub>i,j</sub>'' 행렬은 다음과 같이 표현할 수 있다.
:<math>\mathbf{C}_{1,1} = \mathbf{M}_{1} + \mathbf{M}_{4} - \mathbf{M}_{5} + \mathbf{M}_{7}</math>
:<math>\mathbf{C}_{1,2} = \mathbf{M}_{3} + \mathbf{M}_{5}</math>
:<math>\mathbf{C}_{2,1} = \mathbf{M}_{2} + \mathbf{M}_{4}</math>
:<math>\mathbf{C}_{2,2} = \mathbf{M}_{1} - \mathbf{M}_{2} + \mathbf{M}_{3} + \mathbf{M}_{6}</math>

이 과정에서는 곱셈이 사용되지 않기 때문에, 전체 곱셈을 일곱 번의 곱셈과 18번의 덧셈으로 처리할 수 있다. 큰 행렬에 대해서는 행렬의 곱셈이 덧셈보다 더 많은 시간을 필요로 하기 때문에 덧셈을 더 하는 대신 곱셈을 덜 하는 것이 전체적으로 더 효율적이다.

이 과정을 재귀적으로 반복할 경우 총 <math>7 \cdot n^{\log_2 7} - 6 \cdot n^2</math>번의 연산이 필요하다. <math>\log_2 7 = 2.807\cdots</math>이므로 전체 수행 시간은 약 O(n<sup>2.807</sup>)이다. 실제로는 ''n''이 작을 경우 정의에 따라 행렬 곱셈을 하는 경우가 빠를 수도 있기 때문에, 보통 작은 ''n''에 대해서는 일반적인 방법으로 곱셈을 하도록 구현한다.

슈트라센 알고리즘은 속도에 비해 [[수치 안정성]]이 떨어지는 것으로 알려져 있다. 두 행렬 ''A''와 ''B''를 곱한 결과를 ''C''라 할 때, 실제 오차인 <math>\lVert C-AB \rVert</math>는 <math>27 n^2 u \lVert A \rVert \lVert B \rVert + O(u^2)</math>보다 작음이 알려져 있다. 이는 일반적인 행렬 곱셈보다 더 큰 오차이다.<ref>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.</ref>

== 변형된 알고리즘 ==

슈무엘 위노그라드(Shmuel Winograd)는 [[1980년]]에 슈트라센 알고리즘을 변형한 '''위노그라드 알고리즘'''(Winograd algorithm)을 개발하였다. 이 알고리즘은 점근적으로 슈트라센 알고리즘과 동일한 복잡도를 지니지만 덧셈의 횟수를 15번으로 줄인 방법이다. 이 방법에서는 다음과 같은 변수를 쓴다.
:{| cellpadding="3" width="60%"
| <math>\mathbf{S}_1 = \mathbf{A}_{21} + \mathbf{A}_{22}</math> || <math>\mathbf{S}_2 = \mathbf{S}_1 - \mathbf{A}_{11}</math>
|-
| <math>\mathbf{S}_3 = \mathbf{B}_{12} - \mathbf{B}_{11}</math> || <math>\mathbf{S}_4 = \mathbf{B}_{22} - \mathbf{S}_3</math>
|-
| <math>\mathbf{M}_1 = \mathbf{S}_2 \mathbf{S}_4</math> || <math>\mathbf{M}_2 = \mathbf{A}_{11} \mathbf{B}_{11}</math>
|-
| <math>\mathbf{M}_3 = \mathbf{A}_{12} \mathbf{B}_{21}</math> || <math>\mathbf{M}_4 = (\mathbf{A}_{11} - \mathbf{A}_{21}) (\mathbf{B}_{22} - \mathbf{B}_{12})</math>
|-
| <math>\mathbf{M}_5 = \mathbf{S}_1 \mathbf{S}_3</math> || <math>\mathbf{M}_6 = (\mathbf{A}_{12} - \mathbf{S}_2) \mathbf{B}_{22}</math>
|-
| <math>\mathbf{M}_7 = \mathbf{A}_{22} (\mathbf{S}_4 - \mathbf{B}_{21})</math>
|-
| <math>\mathbf{T}_1 = \mathbf{M}_1 + \mathbf{M}_2</math> || <math>\mathbf{T}_2 = \mathbf{T}_1 + \mathbf{M}_4</math>
|}

이 때 행렬 곱셈의 결과는 다음과 같이 주어진다.
:<math>\mathbf{C}_{11} = \mathbf{M}_2 + \mathbf{M}_3</math>
:<math>\mathbf{C}_{12} = \mathbf{T}_1 + \mathbf{M}_5 + \mathbf{M}_6</math>
:<math>\mathbf{C}_{21} = \mathbf{T}_2 - \mathbf{M}_7</math>
:<math>\mathbf{C}_{22} = \mathbf{T}_2 + \mathbf{M}_5</math>

빅터 판(Victor Pan)은 슈트라센 알고리즘에서 행렬을 더 잘게 나눠서 O(n<sup>2.795</sup>)의 시간 안에 행렬을 곱하는 방법을 개발했다. 그는 68×68 행렬은 132,464번의 곱셈으로, 70×70 행렬은 143,640번의 곱셈으로, 72×72 행렬은 155,424번의 곱셈으로 계산이 가능함을 보였다.

[[돈 코퍼스미스]](Don Coppersmith)와 슈무엘 위노그라드는 [[1987년]]에 또 다른 알고리즘인 '''코퍼스미스-위노그라드 알고리즘'''(Coppersmith–Winograd algorithm)을 개발했다. 이 알고리즘 역시 슈트라센 알고리즘처럼 재귀적 발상에서 나온 것으로, 시간 복잡도가 O(n<sup>2.376</sup>)이고 2010년에 Stother가 O(n<sup>2.3737</sup>)로 개선할 때까지 가장 빠른 알고리즘이었다. 이듬해 월리엄스가 O(n<sup>2.3727</sup>)로 개선한 알고리즘이 현존하는 가장 빠른 알고리즘이다. [[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. {{ISBN|0-262-03293-7}}. 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.

== 각주 ==
{{각주}}

== 외부 링크 ==
* {{언어링크|en}} [http://mathworld.wolfram.com/StrassenFormulas.html MathWorld: Strassen's Formula] ([[역행렬#작은 블록으로 나눠서 계산하는 법|역행렬]] 계산에 대한 공식도 포함)

[[분류:수치해석학]]
[[분류:행렬 곱셈 알고리즘]]