행렬 곱셈 — 나누기만으로는 못 이긴다, Strassen이 곱을 줄이는 법

두 행렬을 곱하는 데 정의대로면 $O(N^3)$ 이 든다. 분할 정복으로 지수를 낮출 수 있을까? 순진하게 나누면 안 된다. 블록 곱이 8번이라 지수가 그대로이기 때문이다. Strassen은 그 횟수를 7번으로 줄여 지수를 $\log_2 7 \approx 2.807$ 로 끌어내린다.

이 포스트에서 다루는 내용

나이브 행렬 곱이 왜 $O(N^3)$ 인가
행렬을 2×2 블록으로 나눈 분할 정복 — 왜 $T(N)=8T(N/2)$ 라서 여전히 $N^3$ 인가
Strassen: 곱셈을 7번으로 줄이는 7개의 곱 $P_1,\dots,P_7$
그 7개가 정말 $C$ 의 네 블록을 만드는지 대수로 검증
복잡도 $T(N)=7T(N/2)+\Theta(N^2)=\Theta(N^{\log_2 7})\approx \Theta(N^{2.807})$
이후의 이론적 기록과 “갤럭틱 알고리즘”

나이브 곱은 왜 N³인가

$N \times N$ 행렬 $A$ , $B$ 를 곱해 $C = AB$ 를 만든다. 결과 $C$ 의 원소는

C_{ij} = \sum_{k=1}^{N} A_{ik} B_{kj}

이다. 채워야 할 원소가 $N^2$ 개이고, 원소 하나를 만드는 데 곱셈이 $N$ 번 든다. 곱셈은 모두 $N^2 \cdot N = N^3$ 번이고 덧셈도 그만큼 든다.

앞으로 곱셈 횟수만 세는데, 곱셈이 덧셈보다 비싸서가 아니다. 이 글은 스칼라 덧셈과 곱셈을 모두 상수 시간으로 보는 모델을 쓰므로 두 연산의 단가는 같다. 곱셈 수를 세는 이유는 알고리즘의 구조를 가르는 지표여서다. 뒤에서 보듯 재귀에서 지수를 정하는 것은 절반 크기 곱을 몇 번 하느냐이고, 덧셈은 각 단계에서 $\Theta(N^2)$ 만 더해져 점화식의 낮은 항으로 들어간다.

그러니 전체 실행 시간에는 덧셈도 함께 센다. 곱셈만 센다는 것은 비교의 기준을 좁힌다는 뜻이지 덧셈을 공짜로 본다는 뜻이 아니다.

T_{\text{naive}}(N) = \Theta(N^3)

질문은 하나다. 이보다 빠르게 할 수 있는가?

분할 정복으로 나눠 보기

분할 정복의 문법을 그대로 가져온다. 큰 곱을 작은 곱들로 쪼갤 수 있을까? 행렬을 절반씩 자르면 된다.

$N \times N$ 행렬을 가로·세로로 반씩 갈라 $\frac{N}{2}\times\frac{N}{2}$ 짜리 네 블록으로 본다. 이때 행렬은 “숫자의 2차원 배열”일 뿐이므로, 블록 자체를 하나의 원소처럼 취급해 $2\times2$ 행렬처럼 곱할 수 있다.

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},\quad C = \begin{pmatrix} C_{11} & C_{12} \\ C_{21} & C_{22} \end{pmatrix}

블록끼리도 보통 행렬 곱과 똑같은 규칙이 성립한다.

\begin{aligned} C_{11} &= A_{11}B_{11} + A_{12}B_{21} & C_{12} &= A_{11}B_{12} + A_{12}B_{22} \\ C_{21} &= A_{21}B_{11} + A_{22}B_{21} & C_{22} &= A_{21}B_{12} + A_{22}B_{22} \end{aligned}

N×N 행렬을 2×2 블록으로 나누면, 블록을 원소처럼 다뤄 재귀적으로 곱할 수 있다. 하지만 블록 곱이 8번이라 T(N)=8T(N/2)로 여전히 Θ(N³)이다.

여기서 블록끼리의 곱 $A_{ij}B_{jk}$ 는 각각 $\frac{N}{2}\times\frac{N}{2}$ 행렬 곱, 즉 절반 크기의 같은 문제다. 위 식에 곱이 몇 번 나오는지 세어 보면 여덟 번( $A_{11}B_{11}, A_{12}B_{21}, \dots$ )이다. 점화식은

T(N) = 8\,T\!\left(\tfrac{N}{2}\right) + \Theta(N^2)

가 된다. 블록을 더하는 비용이 $\Theta(N^2)$ 이다. merge sort의 점화식을 대입법으로 풀었던 것과 같은 방식으로 펼쳐 보자. 덧셈 항을 잠시 무시하고 재귀 항만 따라가면

T(N) = 8\,T\!\left(\tfrac{N}{2}\right) = 8^2\,T\!\left(\tfrac{N}{4}\right) = \cdots = 8^{\log_2 N}\,T(1) = N^{\log_2 8} = N^3

이다. $8^{\log_2 N} = N^{\log_2 8} = N^3$ 이라는 지수 법칙이 핵심이다. 여기에 덧셈의 $\Theta(N^2)$ 를 더해도 $N^3$ 이 압도하므로 결과는 그대로 $\Theta(N^3)$ 이다.

나누기만으로는 못 이긴다

블록으로 나눈 분할 정복은 나이브와 똑같은 $\Theta(N^3)$ 이다. 오히려 재귀 호출과 블록 덧셈의 오버헤드 때문에 실제로는 더 느리다. 재귀 호출이 $a$ 번이고 크기가 $b$ 분의 1로 줄면 지수는 $\log_b a$ 이므로, 지수를 정하는 것은 절반 크기 곱을 몇 번 하느냐다. 블록 곱이 $8$ 번인 동안 지수는 $\log_2 8 = 3$ 에서 움직이지 않는다.

그렇다면 할 일이 분명해진다. 블록 곱을 8번보다 적게 하면 된다.

Strassen: 곱을 7번으로

1969년 Strassen은 $2\times2$ 블록 곱을 곱셈 7번으로 해내는 방법을 찾았다. 먼저 블록들의 합과 차로 일곱 개의 곱 $P_1,\dots,P_7$ 을 정의한다. 이름은 임의의 라벨일 뿐이라 $R, S, T, \dots$ 로 적어도 된다.

\begin{aligned} P_1 &= A_{11}\,(B_{12} - B_{22}) \\ P_2 &= (A_{11} + A_{12})\,B_{22} \\ P_3 &= (A_{21} + A_{22})\,B_{11} \\ P_4 &= A_{22}\,(B_{21} - B_{11}) \\ P_5 &= (A_{11} + A_{22})\,(B_{11} + B_{22}) \\ P_6 &= (A_{12} - A_{22})\,(B_{21} + B_{22}) \\ P_7 &= (A_{11} - A_{21})\,(B_{11} + B_{12}) \end{aligned}

각 $P_i$ 는 괄호 안에서 덧셈·뺄셈을 한 뒤 곱을 딱 한 번 한다. 여기 든 곱셈은 모두 일곱 번이다. 이제 이 일곱 개를 더하고 빼서 $C$ 의 네 블록을 만든다.

\begin{aligned} C_{11} &= P_5 + P_4 - P_2 + P_6 \\ C_{12} &= P_1 + P_2 \\ C_{21} &= P_3 + P_4 \\ C_{22} &= P_5 + P_1 - P_3 - P_7 \end{aligned}

이 조합에는 덧셈·뺄셈만 있고 곱셈이 없다. 곱셈은 오직 $P_1,\dots,P_7$ 을 만들 때의 일곱 번뿐이다.

정리 17개의 곱으로 충분하다

위의 $P_1,\dots,P_7$ 에 대해

C_{11}=P_5+P_4-P_2+P_6,\ \ C_{12}=P_1+P_2,\ \ C_{21}=P_3+P_4,\ \ C_{22}=P_5+P_1-P_3-P_7

은 블록 곱 정의 $C_{11}=A_{11}B_{11}+A_{12}B_{21}$ 등과 정확히 일치한다. 즉 곱셈 7번으로 $C$ 의 네 블록이 모두 재구성된다.

증명. 네 블록을 각각 전개해 대조한다. 대표로 가장 복잡한 $C_{11}$ 을 보이면 나머지는 같은 방식으로 따라온다.

$C_{11}=P_5+P_4-P_2+P_6$ 을 전개한다.

\begin{aligned} P_5 &= A_{11}B_{11} + A_{11}B_{22} + A_{22}B_{11} + A_{22}B_{22} \\ P_4 &= A_{22}B_{21} - A_{22}B_{11} \\ -P_2 &= -A_{11}B_{22} - A_{12}B_{22} \\ P_6 &= A_{12}B_{21} + A_{12}B_{22} - A_{22}B_{21} - A_{22}B_{22} \end{aligned}

네 줄을 더하면 $A_{11}B_{22}$ , $A_{22}B_{11}$ , $A_{22}B_{22}$ , $A_{22}B_{21}$ , $A_{12}B_{22}$ 항이 모두 부호가 맞아 소거되고, $A_{11}B_{11} + A_{12}B_{21}$ 만 남는다. 이는 정확히 $C_{11}$ 의 정의다.

같은 계산을 나머지 셋에도 적용하면 $C_{12}=P_1+P_2=A_{11}B_{12}+A_{12}B_{22}$ , $C_{21}=P_3+P_4=A_{21}B_{11}+A_{22}B_{21}$ , $C_{22}=P_5+P_1-P_3-P_7=A_{21}B_{12}+A_{22}B_{22}$ 가 각각 정의와 일치한다. 네 블록이 모두 재구성되므로 곱셈 7번으로 충분하다. ∎

정리 1은 이 일곱 개가 답이 됨을 보장한다. 하지만 왜 하필 이 일곱 개인가, 그리고 곱셈을 6번으로는 줄일 수 없는가는 별도의 이야기다. 이 동기와 최적성은 추가 설명 — Strassen의 7은 어디서 왔고 왜 최소인가에서 다룬다.

복잡도

블록 곱이 7번이므로 점화식은

T(N) = 7\,T\!\left(\tfrac{N}{2}\right) + \Theta(N^2)

이다. $\Theta(N^2)$ 는 $P_i$ 를 만들고 $C$ 블록을 조립하는 데 드는 열여덟 번의 블록 덧셈·뺄셈 비용이다. 재귀 항을 펼치면

T(N) = 7\,T\!\left(\tfrac{N}{2}\right) = 7^2\,T\!\left(\tfrac{N}{4}\right) = \cdots = 7^{\log_2 N}\,T(1) = N^{\log_2 7}

이고, 덧셈의 $\Theta(N^2)$ 는 $N^{\log_2 7}$ 가 압도하므로( $\log_2 7 > 2$ ) 최종 복잡도는

T_{\text{Strassen}}(N) = \Theta\!\left(N^{\log_2 7}\right) = \Theta\!\left(N^{2.807\ldots}\right)

이다.

지수가 log₂7인 이유

$8^{\log_2 N} = N^{\log_2 8} = N^3$ 이었던 것과 똑같이, $7^{\log_2 N} = N^{\log_2 7}$ 이다. 여기서 $\log_2 7 = 2.807\ldots$ 이다(흔히 보이는 $2.89$ 는 $\log_2 7$ 이 아니라 잘못 계산한 값이다 — $2^{2.807}\approx 7$ 로 검산된다). 곱셈을 단 한 번 줄인 것이 지수를 $3 \to 2.807$ 로 바꾼다.

나이브 분할 정복은 재귀 가지가 8개라 지수가 log₂8=3, Strassen은 7개라 log₂7≈2.807. 가지 하나 차이가 복잡도의 지수를 바꾼다.

의사코드

블록을 재귀로 곱하고, 7개의 곱을 조립하는 뼈대는 다음과 같다. 크기가 $1$ 이 되면 직접 곱한다.

// A, B: N×N 행렬 (N은 2의 거듭제곱으로 가정)
Matrix strassen(const Matrix& A, const Matrix& B) {
    int N = A.size();
    if (N == 1) return { A[0][0] * B[0][0] };   // 기저: 스칼라 곱

    // 1. 네 블록으로 분할  (각 (N/2)×(N/2))
    auto [A11, A12, A21, A22] = split(A);
    auto [B11, B12, B21, B22] = split(B);

    // 2. 곱은 딱 7번 — 각 호출이 절반 크기의 재귀
    Matrix P1 = strassen(A11,           B12 - B22);
    Matrix P2 = strassen(A11 + A12,     B22);
    Matrix P3 = strassen(A21 + A22,     B11);
    Matrix P4 = strassen(A22,           B21 - B11);
    Matrix P5 = strassen(A11 + A22,     B11 + B22);
    Matrix P6 = strassen(A12 - A22,     B21 + B22);
    Matrix P7 = strassen(A11 - A21,     B11 + B12);

    // 3. 덧셈·뺄셈만으로 C의 네 블록 조립
    Matrix C11 = P5 + P4 - P2 + P6;
    Matrix C12 = P1 + P2;
    Matrix C21 = P3 + P4;
    Matrix C22 = P5 + P1 - P3 - P7;

    return combine(C11, C12, C21, C22);
}

곱셈이 일어나는 곳은 strassen 재귀 호출 일곱 줄뿐이다. 나머지 행렬 덧셈·뺄셈은 $\Theta(N^2)$ 로, 점화식의 상수항에 흡수된다.

현실에서는

Strassen이 항상 이기는 것은 아니다. 재귀·블록 분할·여분의 덧셈이 오버헤드로 붙어서, 작은 행렬에서는 나이브가 더 빠르다. 실제 구현은 블록이 어느 크기 이하로 작아지면 나이브 곱으로 전환한다. Strassen의 이점은 행렬이 충분히 클 때 지수 $2.807$ 이 $3$ 을 압도하며 드러난다.

그 뒤의 기록들

Strassen이 지수를 $3$ 아래로 처음 끌어내린 뒤, 행렬 곱의 지수 $\omega$ 를 낮추는 경쟁이 이어졌다.

1987년, Coppersmith–Winograd: $O(N^{2.376})$ .
2014년, Le Gall: $O(N^{2.3728639})$ 로 당시 기록을 갱신.
이후로도 아주 미세한 개선이 계속되었지만, 이론적 하한은 $\Omega(N^2)$ (결과가 $N^2$ 개이므로 최소한 한 번씩은 써야 한다)이고, 진짜 지수 $\omega$ 가 $2$ 인지는 아직 열린 문제다.

갤럭틱 알고리즘

Coppersmith–Winograd 계열의 알고리즘은 지수는 낮지만 숨은 상수가 천문학적으로 커서, 실제로 이득을 보려면 현실에 존재하지 않을 만큼 거대한 행렬이 필요하다. 이런 알고리즘을 갤럭틱 알고리즘(galactic algorithm) 이라 부른다. 이론적 지수를 낮추는 의미는 있지만, 실무에서 실제로 쓰이는 것은 여전히 나이브 곱이나 Strassen(그마저도 큰 행렬에 한해)이다.

마치며

지수를 정하는 것은 얼마나 잘게 나누느냐가 아니라 절반 크기의 곱을 몇 번 하느냐였다. 순진한 분할 정복은 그 횟수가 $8$ 이라 나이브와 같은 $N^3$ 에 머물렀고, Strassen은 $7$ 로 줄여 $\log_2 7 \approx 2.807$ 을 얻었다. 재귀 호출 수가 지수에 로그로 들어가므로 한 번의 차이가 지수를 바꾼다.

남은 질문, “왜 하필 그 일곱 개이고 여섯 개로는 안 되는가”는 추가 설명에서 이어 간다.

같은 요령이 행렬보다 9년 먼저, 훨씬 단순한 무대에 등장했다. $n$ 자리 정수 곱을 4번에서 3번으로 줄인 카라츠바 알고리즘이다.