Strassen Algorithm

표준 행렬 곱의 벽

$n \times n$ 행렬 $A$와 $B$의 곱 $C = AB$를 정의대로 계산하면 각 $C_{ij} = \sum_{k=1}^{n} A_{ik} B_{kj}$에 $n$번의 곱셈이 들고, 원소가 $n^2$개이므로 총 $\Theta(n^3)$번의 스칼라 곱셈이 필요하다.

이를 블록 행렬 곱으로 분할해 보자. $n$이 짝수일 때 각 행렬을 $n/2 \times n/2$ 블록 네 개로 나누면

$A = \begin{pmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{pmatrix}, \quad B = \begin{pmatrix} B_{11} & B_{12} \\ B_{21} & B_{22} \end{pmatrix}$

이고, 곱은 다음과 같이 8개의 블록 곱으로 표현된다.

$C = \begin{pmatrix} A_{11}B_{11} + A_{12}B_{21} & A_{11}B_{12} + A_{12}B_{22} \\ A_{21}B_{11} + A_{22}B_{21} & A_{21}B_{12} + A_{22}B_{22} \end{pmatrix}$

이 방식의 점화식은 $T(n) = 8T(n/2) + \Theta(n^2)$이며, 마스터 정리로 풀면 $a = 8 = 2^3 = b^d$이므로 $T(n) = \Theta(n^3 \log n)$이 된다. 분할 정복이 오히려 손해를 본 셈이다. 단순한 블록 분해로는 $\Theta(n^3)$을 깰 수 없다는 것이 이전까지의 상식이었다.

Strassen의 7개 곱셈

Strassen은 여덟 번의 블록 곱셈 대신 일곱 번만 사용하는 항등식을 발견했다. 다음 일곱 개의 중간 행렬을 정의하자.

$$\begin{aligned} 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}) \end{aligned}$$

일곱 개의 행렬 곱 $M_1, \ldots, M_7$만 계산하면, $C$의 네 블록을 덧·뺄셈만으로 조합할 수 있다.

$$\begin{aligned} 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 \end{aligned}$$

이 항등식이 왜 성립하는지는 각 $M_i$를 전개해 대입하면 확인할 수 있다. 예컨대 $C_{11}$에 $M_1 + M_4 - M_5 + M_7$을 대입하면

$$\begin{aligned} &(A_{11}+A_{22})(B_{11}+B_{22}) + A_{22}(B_{21}-B_{11}) - (A_{11}+A_{12})B_{22} + (A_{12}-A_{22})(B_{21}+B_{22}) \\ &= A_{11}B_{11} + A_{12}B_{21} \end{aligned}$$

으로 정확히 표준 공식이 재현된다. 나머지 세 블록도 마찬가지다.

점화식과 복잡도

블록 곱 7번과 블록 덧·뺄셈 $\Theta(n^2)$의 조합이므로 점화식은 다음과 같다.

$T(n) = 7T\!\left(\frac{n}{2}\right) + \Theta(n^2)$

마스터 정리의 단순 형태에 $a = 7$, $b = 2$, $d = 2$를 대입하면 $b^d = 4 < 7 = a$이므로

$T(n) = \Theta\!\left(n^{\log_2 7}\right) \approx \Theta\!\left(n^{2.807}\right)$

$\log_2 7 \approx 2.807$이라는 지수는 표준 $n^3$보다 분명히 작다. $n = 1024$일 때 표준 방법은 약 $10^9$번의 곱셈이 필요하지만, Strassen은 약 $10^{8.4}$번으로 줄어든다.

실전에서의 트레이드오프

Strassen의 점근 복잡도는 우수하지만, 실전에서 바로 표준 알고리즘을 대체하지는 않는다. 세 가지 걸림돌이 있다.

• 상수 인자가 크다. Strassen은 7번의 곱셈 대신 18번의 덧·뺄셈이 필요하다(표준 블록법은 8번의 곱셈과 4번의 덧셈). 작은 $n$에서는 이 상수가 곱셈 절감분을 넘어선다. 실용적인 임계값은 CPU 캐시 크기에 따라 다르지만 대개 $n \geq 100{\sim}1000$ 이상에서 이득이 시작된다.
• 수치 안정성이 떨어진다. 덧·뺄셈이 반복되면서 부동소수점 오차가 누적되어, 표준 방법보다 정밀도 손실이 크다. BLAS¹ 같은 수치 라이브러리는 정확성이 중요한 상황에서는 Strassen을 쓰지 않는다.
• 메모리 접근 패턴이 복잡하다. 현대 CPU는 캐시 지역성cache locality이 성능을 크게 좌우하는데, Strassen의 중간 행렬 $M_1, \ldots, M_7$은 추가 메모리 할당과 비순차 접근을 요구한다. 블록화된 표준 알고리즘이 하드웨어에 더 잘 맞는다.

이런 이유로 NumPy, Eigen, MKL 같은 실전 라이브러리는 기본적으로 표준 방법을 쓰고, 매우 큰 행렬(수천 차원 이상)에서만 선택적으로 Strassen을 적용한다.

---

출처

• Strassen, V. (1969) 'Gaussian elimination is not optimal', Numerische Mathematik, 13(4), pp. 354–356.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C. (2022) Introduction to Algorithms. 4th edn. Cambridge, MA: MIT Press, Chapter 4.2.
• Williams, V. V. (2012) 'Multiplying matrices faster than Coppersmith–Winograd', Proceedings of the 44th Symposium on Theory of Computing (STOC), pp. 887–898.
• Duan, R., Wu, H. and Zhou, R. (2022) 'Faster matrix multiplication via asymmetric hashing', arXiv:2210.10173.

Footnotes

1. BLAS(Basic Linear Algebra Subprograms) — 선형 대수 연산의 표준 인터페이스. 1970년대 후반에 정의되었으며, LAPACK, NumPy, MATLAB 등 거의 모든 수치 라이브러리의 저수준 백엔드로 사용된다. 구현으로는 Intel MKL, OpenBLAS, Apple Accelerate 등이 있다. ↩