5년 전에 쓰다 만 글이 보여서 퇴고를 거쳐 올려둔다. 졸면서 쓰는 게 퇴고인가? 잘 모르겠다.

개요

알고리즘 문제를 (메모리 비트 길이 만큼)아주 작은 크기의 문제로 분할하여, 그 문제에 입력 가능한 모든 조합을 미리 계산해서 기억하고 꺼내다 쓰는 기법이다. $\log(n)$ 내지 $\log^2(n)$ 만큼 시간복잡도를 떨어트린다. 실용성에는 이견의 여지가 있겠으나, 패러다임을 적용한 알고리즘의 구현은 쉬운 편이다. 1970년 발표된 논문의 저자 네 명이 모스크바 대학 소속이라 Four Russians라는 이름이 붙었다고 알려져 있다. 방향 그래프의 이행적 폐쇄(transitive closure)를 찾는 기법의 일환으로 이진 행렬 곱셈(boolean matrix multiplication, 이하 BMM)을 사용하는데, 이 과정을 최적화하는 기법으로 처음 소개[1]되었다.

50년도 더 된 러시아어 논문을 출처까지 찾아가며 자세히 읽고 싶지 않아, 반 페이지 정도 되는 핵심 아이디어만 떼어다 정리해둔다.

다대다 사상(mapping)의 합성

두 개의 다대다 사상(multi-valued mapping) $\alpha: A \rightarrow B$와 $\beta: B \rightarrow C$가 주어졌을 때, 합성 사상 $\beta \circ \alpha: A \rightarrow C$을 계산하는 문제.[*]

  • 전처리
    • $B$를 $\lfloor \lg n \rfloor$ 크기로 분할하여 순서대로 $B_1, B_2, \cdots, B_{n’}$라고 부르자($n’ \le \lceil n /\lg n \rceil + 1$).
    • $\alpha_i : A \rightarrow B_i$, $\beta_i : B_i \rightarrow C$라 하자.
    • 당연히 $\beta \circ \alpha = \bigcup_{i=1}^{n’} \beta_i \circ \alpha_i$이다.
    • 모든 $b \subseteq B_i$에 대해 $\beta_i(b) := {c \in C: \exists x \in b, (x, c) \in \beta}$를 계산한다.
      • 가능한 $b$의 경우의 수가 $2^{\lg n} \in O(n)$이므로, 테이블을 계산하는 데에는 $O(nk)$ 시간이 필요하다.
    • 메모이제이션에 필요한 시간은 $O(n’) \times O(nk) = O(n^2 k / \lg n)$이다.
  • 계산
    • $a \in A$에 대해
      • 모든 $i \le n’$마다 $b_{a,i} := {b \in B_i: (a, b) \in \alpha}$를 계산한다.
      • $\beta \circ \alpha(a) := \bigcup_{i=1}^{n’} \beta_i(b_{a,i})$를 계산한다.
      • 이때, $b_{a,i}$의 경우의 수가 $O(n)$이므로, $O(nk)$ 시간이 필요하다.
    • 계산하는 데 걸리는 시간은 $O(mn’k) = O(mnk / \lg n)$이다.
  • 정리
    • 따라서 합성 사상을 계산하는 데 걸리는 시간은 $O((m + n)nk / \lg n)$이다.
    • $m = n = k$인 경우 $O(n^3 / \lg n)$.

요즘 표현으로 Four Russians 재해석하면

Word RAM이라는 게산 모델을 사용한다. 고전 알고리즘에 등장하는 RAM 계산 모델에서는 임의 크기 메모리 접근과 임의의 수에 대해 산술 연산을 할 수 있다면, Word RAM은 단위 시간 안에 $w = O(\lg n)$ 비트의 산술/비트 연산을 수행할 수 있는 모델을 의미한다. $O(n^c)$ 크기의 저장공간을 사용하려면 메모리의 주소 길이가 적어도 $\Omega(\lg n)$이어야 하기 때문에, RAM보다 현실적인 조건의 계산 모델이라 할 수 있다.

BMM: 행렬 $A, B \in {0, 1}^{n \times n}$를 입력받아 $C := A \times B$ 를 반환하는 문제.

  • 편의상 $t | n, 2^t = n$이라 가정한다(예: $n = 2^t = 2^{2^u}$ for $u \in \mathbb{N}$). $t := \lg n$라 할 때,

    • A는 길이 $t$의 가로 벡터로 구성된 $n \times (n / t)$ 행렬 $\bar{A}$로 볼 수 있고,
    • B는 길이 $t$의 세로 벡터로 구성된 $(n / t) \times n$ 행렬 $\bar{B}$로 볼 수 있다.

  • $C$의 각 요소 $c_{ij} = \sum_{k=1}^{t} a_{ik} b_{kj} = \sum_{k=1}^{n / t} (\bar{A}{ik} \wedge \bar{B}{kj})$

    • ($\wedge$: 내적 결과 하나라도 1인 비트가 있으면 1을 반환하는 연산이라고 대충 봐달라)

  • 계산하고자 하는 행렬의 각 요소마다 $O(n / t)$번의 비트 연산(and -> cmp 0) -> 총 $O(n^3 / t)$번

  • 이 비트 곱셈의 모든 입력과 대응하는 출력을 미리 계산하고 기억하는 과정이 핵심이다.

    • 모든 입력 경우의 수 $2^t \times 2^t = O(n^2)$

  • 이 접근방법 또한 똑같은 시간 복잡도($O(n^3 / \lg n)$)를 가진다.

Strassen[3]이나 Coppersmith-Winograd[5] 쓰면 $\tilde{o}(n^3)$ 달성할 수 있지 않나?

Strassen 알고리즘[3]은 이 방법론이 나오기 1년 전인 1969년에 발표되었다. 환의 대수적 속성을 이용해 불필요한 항을 더했다가 빼는 방식으로 복잡도의 다항식 차수를 떨어트린 경우인데, 그 이후 80년대까지 대수적인 최적화 계보는 Timothy Chan의 노트로, Coppersmith-Winograd 알고리즘의 핵심 아이디어는 Matthew Anderson과 Siddharth Barman의 노트로 갈음한다.

몇몇 노트를 보니 조합적인 알고리즘이라 부르는데, 잘 정의된 용어인지는 잘 모르겠다. (VV Williams의 알고리즘 하한 가설에 관련된 서베이 페이퍼[4]에서도 비스무리한 말이 있었다.)

대수적 최적화가 적용되지 못하는 대표적 사례로 min-plus matrix multiplication이 있다. $(\mathbb{R}, +, \times)$를 $(\mathbb{R}, \min, +)$로 바꿨을 뿐이지만 Strassen 류의 알고리즘이 작동하지 않는다. 후자는 환(ring)의 대수적 속성을 만족하지 못하는데, 첫 번째 연산자인 $\min$이 역원을 가지는 연산자가 아니기 때문이다.

더 보기

  • Jeff Erickson의 강의 노트 중 Advanced Dynamic Programming 챕터를 보면 언젠가 작성 예정이라고 나와 있다.
  • 최장길이 공통 부분수열(Longest Common Subsequence, LCS)/편집거리(Edit Distance, ED)에 적용한 예시가 매우 볼만한데, 링크[2]로 대체한다. DP 테이블을 $O(\frac{\log n}{\log \Sigma}) \times O(\frac{\log n}{\log \Sigma})$ 크기의 비계로 만들고, 좌측/상단 distance의 변위(0 또는 $\pm 1$) 및 해당구간 문자 입력 시퀀스만 입력받아 DP 테이블을 계산한다.

References

[1] Arlazarov, V. L. V., Dinitz, Y. A., Kronrod, M. A., & Faradzhev, I. (1970). On economical construction of the transitive closure of an oriented graph. In Doklady Akademii Nauk (Vol. 194, No. 3, pp. 487-488). Russian Academy of Sciences.

[2] Masek, W. J., & Paterson, M. S. (1980). A faster algorithm computing string edit distances. Journal of Computer and System sciences, 20(1), 18-31.

[3] Strassen, V. (1969). Gaussian elimination is not optimal. Numerische mathematik, 13(4), 354-356.

[4] Williams, V. V. (2018). On some fine-grained questions in algorithms and complexity. In Proceedings of the international congress of mathematicians: Rio de janeiro 2018 (pp. 3447-3487).

[5] Coppersmith, D., & Winograd, S. (1987, January). Matrix multiplication via arithmetic progressions. In Proceedings of the nineteenth annual ACM symposium on Theory of computing (pp. 1-6).

각주

[*] 다대다 사상은 Cartesian product의 subset과 같다. 따라서 $\alpha \subseteq A \times B$와 $\beta \subseteq B ₩\times C$로 다시 쓸 수 있다. $|A| = m, |B| = n, |C| = k$라 하면 $${0, 1}^{m \times n} \times {0, 1}^{n \times k} \rightarrow {0, 1}^{m \times k}$$이므로 BMM이라 할 수도 있다.