슈트라센 알고리즘

선형대수학에서 슈트라센 알고리즘은 독일의 수학자 폴커 슈트라센(Volker Strassen)이 1969년에 개발한 행렬 곱셈 알고리즘이다. 정의에 따라 n×n 크기의 두 행렬을 곱하면 O(n³)의 시간이 소요되지만 이 알고리즘은 대략 O(n^2.81)의 시간이 소요된다.

알고리즘

A와 B를 체 F에 대한 정사각행렬이라고 하자. 두 행렬의 곱 C는 다음과 같다.

${\displaystyle \mathbf {C} =\mathbf {A} \mathbf {B} \qquad \mathbf {A} ,\mathbf {B} ,\mathbf {C} \in F^{2^{n}\times 2^{n}}}$

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

이제 A, B, C를 같은 크기의 정사각행렬 네 개로 나눈다.

${\displaystyle \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}}}$

이 때,

${\displaystyle \mathbf {A} _{i,j},\mathbf {B} _{i,j},\mathbf {C} _{i,j}\in F^{2^{n-1}\times 2^{n-1}}}$

따라서 다음이 성립한다.

${\displaystyle \mathbf {C} _{1,1}=\mathbf {A} _{1,1}\mathbf {B} _{1,1}+\mathbf {A} _{1,2}\mathbf {B} _{2,1}}$

${\displaystyle \mathbf {C} _{1,2}=\mathbf {A} _{1,1}\mathbf {B} _{1,2}+\mathbf {A} _{1,2}\mathbf {B} _{2,2}}$

${\displaystyle \mathbf {C} _{2,1}=\mathbf {A} _{2,1}\mathbf {B} _{1,1}+\mathbf {A} _{2,2}\mathbf {B} _{2,1}}$

${\displaystyle \mathbf {C} _{2,2}=\mathbf {A} _{2,1}\mathbf {B} _{1,2}+\mathbf {A} _{2,2}\mathbf {B} _{2,2}}$

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

이제 다음과 같은 행렬을 정의한다.

${\displaystyle \mathbf {M} _{1}:=(\mathbf {A} _{1,1}+\mathbf {A} _{2,2})(\mathbf {B} _{1,1}+\mathbf {B} _{2,2})}$

${\displaystyle \mathbf {M} _{2}:=(\mathbf {A} _{2,1}+\mathbf {A} _{2,2})\mathbf {B} _{1,1}}$

${\displaystyle \mathbf {M} _{3}:=\mathbf {A} _{1,1}(\mathbf {B} _{1,2}-\mathbf {B} _{2,2})}$

${\displaystyle \mathbf {M} _{4}:=\mathbf {A} _{2,2}(\mathbf {B} _{2,1}-\mathbf {B} _{1,1})}$

${\displaystyle \mathbf {M} _{5}:=(\mathbf {A} _{1,1}+\mathbf {A} _{1,2})\mathbf {B} _{2,2}}$

${\displaystyle \mathbf {M} _{6}:=(\mathbf {A} _{2,1}-\mathbf {A} _{1,1})(\mathbf {B} _{1,1}+\mathbf {B} _{1,2})}$

${\displaystyle \mathbf {M} _{7}:=(\mathbf {A} _{1,2}-\mathbf {A} _{2,2})(\mathbf {B} _{2,1}+\mathbf {B} _{2,2})}$

이 M_k 행렬들은 C_i,j 행렬을 표현하는 데 쓰이는데, 이 행렬들을 계산하는 데는 일곱 번의 곱셈(각 변수마다 한 번씩)과 10번의 덧셈이 필요하다. 이제 C_i,j 행렬은 다음과 같이 표현할 수 있다.

${\displaystyle \mathbf {C} _{1,1}=\mathbf {M} _{1}+\mathbf {M} _{4}-\mathbf {M} _{5}+\mathbf {M} _{7}}$

${\displaystyle \mathbf {C} _{1,2}=\mathbf {M} _{3}+\mathbf {M} _{5}}$

${\displaystyle \mathbf {C} _{2,1}=\mathbf {M} _{2}+\mathbf {M} _{4}}$

${\displaystyle \mathbf {C} _{2,2}=\mathbf {M} _{1}-\mathbf {M} _{2}+\mathbf {M} _{3}+\mathbf {M} _{6}}$

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

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

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

변형된 알고리즘

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

${\displaystyle \mathbf {S} _{1}=\mathbf {A} _{21}+\mathbf {A} _{22}}$	${\displaystyle \mathbf {S} _{2}=\mathbf {S} _{1}-\mathbf {A} _{11}}$
${\displaystyle \mathbf {S} _{3}=\mathbf {B} _{12}-\mathbf {B} _{11}}$	${\displaystyle \mathbf {S} _{4}=\mathbf {B} _{22}-\mathbf {S} _{3}}$
${\displaystyle \mathbf {M} _{1}=\mathbf {S} _{2}\mathbf {S} _{4}}$	${\displaystyle \mathbf {M} _{2}=\mathbf {A} _{11}\mathbf {B} _{11}}$
${\displaystyle \mathbf {M} _{3}=\mathbf {A} _{12}\mathbf {B} _{21}}$	${\displaystyle \mathbf {M} _{4}=(\mathbf {A} _{11}-\mathbf {A} _{21})(\mathbf {B} _{22}-\mathbf {B} _{12})}$
${\displaystyle \mathbf {M} _{5}=\mathbf {S} _{1}\mathbf {S} _{3}}$	${\displaystyle \mathbf {M} _{6}=(\mathbf {A} _{12}-\mathbf {S} _{2})\mathbf {B} _{22}}$
${\displaystyle \mathbf {M} _{7}=\mathbf {A} _{22}(\mathbf {S} _{4}-\mathbf {B} _{21})}$
${\displaystyle \mathbf {T} _{1}=\mathbf {M} _{1}+\mathbf {M} _{2}}$	${\displaystyle \mathbf {T} _{2}=\mathbf {T} _{1}+\mathbf {M} _{4}}$

이 때 행렬 곱셈의 결과는 다음과 같이 주어진다.

${\displaystyle \mathbf {C} _{11}=\mathbf {M} _{2}+\mathbf {M} _{3}}$

${\displaystyle \mathbf {C} _{12}=\mathbf {T} _{1}+\mathbf {M} _{5}+\mathbf {M} _{6}}$

${\displaystyle \mathbf {C} _{21}=\mathbf {T} _{2}-\mathbf {M} _{7}}$

${\displaystyle \mathbf {C} _{22}=\mathbf {T} _{2}+\mathbf {M} _{5}}$

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

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

각주

1. 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.

외부 링크

• (영어) MathWorld: Strassen's Formula (역행렬 계산에 대한 공식도 포함)