슈트라센 알고리즘

선형대수학에서 **슈트라센 알고리즘**은 독일의 수학자 폴커 슈트라센(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} 

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

이제 다음과 같은 행렬을 정의한다.
:\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})

이 *M<sub>k</sub>* 행렬들은 *C<sub>i,j</sub>* 행렬을 표현하는 데 쓰이는데, 이 행렬들을 계산하는 데는 일곱 번의 곱셈(각 변수마다 한 번씩)과 10번의 덧셈이 필요하다. 이제 *C<sub>i,j</sub>* 행렬은 다음과 같이 표현할 수 있다.
:\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)보다 작음이 알려져 있다. 이는 일반적인 행렬 곱셈보다 더 큰 오차이다.

## 변형된 알고리즘

슈무엘 위노그라드(Shmuel Winograd)는 1980년에 슈트라센 알고리즘을 변형한 **위노그라드 알고리즘**(Winograd algorithm)을 개발하였다. 이 알고리즘은 점근적으로 슈트라센 알고리즘과 동일한 복잡도를 지니지만 덧셈의 횟수를 15번으로 줄인 방법이다. 이 방법에서는 다음과 같은 변수를 쓴다.
:

이 때 행렬 곱셈의 결과는 다음과 같이 주어진다.
:\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.

## 각주

## 외부 링크
*  MathWorld: Strassen's Formula (역행렬 계산에 대한 공식도 포함)

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