[알고리즘설계] 행렬 곱셈을 위한 스트라센 알고리즘

[알고리즘 설계] 행렬 곱셉을 위한 스트라센 알고리즘

1. 기본적인 행렬의 곱 연산

• 행렬 A와 B가 n * n의 정사각 행렬일 경우, 두 행렬의 곱 C = A * B를 정의하면, cij = Σ(k=1~n) aik * bkj (cij 는 행렬 C의 원소).

SQUARE-MATRIX-MULTIPLY(A,B)
    n= A.rows
    C는 새로운 n * n 행렬이라고 하자.
    for i =1 to n
        for j=1 to n
            cij = 0
            for k=1 to n
                cij = cij + aik * bkj
    return C

• 3중 루프의 각 루프는 반복을 정확히 n번 수행하고 cij = cij + aik * bkj 이 행은 상수시간이 걸리므로 이 프로시저는 Θ(n^3) 시간이 걸린다.
• 행렬 곱셈의 자연스러운 정의 자체가 많은 곱셈을 포함하고 있기 때문에 처음에는 어떤 행렬 곱셈 알고리즘도 하계가 Ω(n^3) 시간이 걸릴수밖에 없다고 생각할 수도 있지만, 이보다 짧은 알고리즘은 꽤 존재.
• 스트라센 알고리즘은 Θ(n^lg7) 의 수행시간을 가진다.

2. 단순한 분할정복 알고리즘

• 분할 정복 알고리즘을 통해 행렬의 곱 C= A * B 를 계산할때는 각 n * n 행렬의 n이 정확하게 2의 거듭제곱이 된다고 가정. 각 단계에서 n * n 행렬을 네개의 n/2 * n/2로 나눈다.
• A,B,C 행렬을 각각 네개의 n/2 * n/2 행렬로 나눈다고 하면, A=(A11 A12 A21 A22), B=(B11 B12 B21 B22), C=(C11 C12 C21 C22)로 나누어진다.
• C11 = A11 * B11 + A12 * B21
• C12 = A11 * B12 + A12 * B22
• C21 = A21 * B11 + A22 * B21
• C22 = A21 * B12 + A22 * B22
• 이 등식을 이용하여 재귀적인 분할정복 알고리즘을 만든다.

SQUARE-MATRIX-MULTIPLY-RECURSIVE(A,B)
    n = A.rows
    C는 n * n 행렬이라 하자
    if n==1
        c11 = a11 * b11
    else 
        C11 = SQUARE-MATRIX-MULTIPLY-RECURSIVE(A11,B11) +
              SQUARE-MATRIX-MULTIPLY-RECURSIVE(A12,B21)
        C12 = SQUARE-MATRIX-MULTIPLY-RECURSIVE(A11,B12) +
              SQUARE-MATRIX-MULTIPLY-RECURSIVE(A12,B22)
        C21 = SQUARE-MATRIX-MULTIPLY-RECURSIVE(A21,B11) +
              SQUARE-MATRIX-MULTIPLY-RECURSIVE(A22,B21)
        C22 = SQUARE-MATRIX-MULTIPLY-RECURSIVE(A21,B12) +
              SQUARE-MATRIX-MULTIPLY-RECURSIVE(A22,B22)
    return C

• 이 경우 새로운 n/2 * n/2 행렬 12개를 만들 때 원 행렬의 행 인덱스 범위와 열 인덱스 범위를 이용하여 부분행렬을 만드므로 Θ(1)에 수행할 수 있다.
• n==1 인 경우는 단순히 하나의 스칼라 곱셈을 하면 되므로 T(1)=Θ(1)이 된다.
• n>1 인 경우는 행렬을 나누는 Θ(1) 과 각 재귀호출이 8번 일어나므로 8 * T(n/2)의 시간이 필요하다. 또한 각 부분행렬이 n^2/4 의 원소를 가지고 있으므로 4번의 행렬 덧셈은 각각 Θ(n^2) 시간이 걸린다.
• 즉 수행시간에 대한 점화식을 만들면 아래와 같이 표현된다.

T(n) = Θ(1)  , if n=1
     = 8T(n/2) + Θ(n^2) , if n>1

• 마스터 정리를 이용하면, T(n) = Θ(n^3)이 된다는 것을 알 수 있다. 이 경우는 일반적인 곱셈연산 수행시간과 다를것이 없다.

3. 스트라센 방법

• 스트라센이 사용한 방법의 핵심은 재귀 트리의 가지 수를 줄이는 것이다.

• 위의 분할정복에선 8번의 재귀호출이 일어나지만 스트라센 방법에선 7번의 재귀호출을 한다. 한번의 행렬 곱셈을 줄이는 대신 덧셈 횟수를 늘린다.

• 스트라센 방법의 네단계.
  1. 부분행렬로 나눈다.
  2. 10개의 행렬 S1,S2, … , S10을 만든다. 각 행렬의 크기는 n/2 * n/2
  3. 1단계에서 만든 부분행렬과 2단계에서 만든 10개의 행렬을 이용해 7개의 행렬 곱 P1,P2,…,P7을 계산한다. 각 행렬 Pi 는 n/2 * n/2 크기이다.
  4. Pi 행렬들의 다양한 조합을 더하거나 빼서 얻고자한 결과 행렬 C의 부분 행렬 C11,C12,C21,C22를 계산한다.
• 1,2,4단계에선 Θ(n^2) 시간이 걸리고, 3단계에선 재귀호출을 7번 한다.

T(n) = Θ(1)  , if n=1
     = 7T(n/2) + Θ(n^2) , if n>1

• T(n)은 마스터 정리에 의해 Θ(n^lg7)이 된다.
• S행렬에 관한 식.
  1. S1 = B12 - B22
  2. S2 = A11 + A12
  3. S3 = A21 + A22
  4. S4 = B21 - B11
  5. S5 = A11 + A22
  6. S6 = B11 + B22
  7. S7 = A12 - A22
  8. S8 = B21 + B22
  9. S9 = A11 - A21
  10. S10 = B11 + B12
• 위 단계에선 n/2 * n/2 행렬을 10번 더하거나 빼므로 Θ(n^2) 시간이 걸린다.
• 다음으론 n/2 * n/2 행렬을 7번 재귀적으로 곱한다.
  1. P1 = A11 * S1 =A11 * B12 - A11 * B22
  2. P2 = S2 * B22 = A11 * B22 + A12 * B22
  3. P3 = S3 * B11 = A21 * B11 + A22 * B11
  4. P4 = A22 * S4 = A22 * B21 - A22 * B11
  5. P5 = S5 * S6 = A11 * B11 + A11 * B22 + A22 * B11 + A22 * B22
  6. P6 = S7 * S8 = A12 * B21 + A12 * B22 - A22 * B21 - A22 * B22
  7. P7 = S9 * S10 = A11 * B11 + A11 * B12 - A21 * B11 - A21 * B12
• 마지막 단계에선 윗 단에서 만든 행렬 Pi를 이용하여 행렬 곱 C의 부분 행렬 4개를 만든다.
  1. C11 = P5 + P4 - P2 + P6
  2. C12 = P1 + P2
  3. C21 = P3 + P4
  4. C22 = P5 + P1 - P3 - P7
• 스트라센 알고리즘은 기본적인 행렬의 곱셈 프로시저보다 점근적으로 더 빠른 알고리즘이기 때문에 처음 발표되었을 때 굉장한 흥분을 불러 일으켰다.
• 현재까지 n * n 행렬을 곱하는 점근적으로 가장 빠르고 효율적인 알고리즘은 Coppersmith 와 Winograd 가 개발한 Ο(n^2.376) 이다.
• 행렬의 곱셈은 n^2의 원소를 채워야하기 때문에 하계는 명백하게 Ω(n^2)이다.
• 스트라센은 실용적인 관점에서 좋은 선택이 아닐 수 있는데, 희소행렬의 경우 희소행렬에 특화된 방법이 더빠르며, 정수가 아닌 값에 대해서는 오차가 일반적인 방법보다 많이 쌓인다. 또한 재귀호출단계에서 생기는 부분행렬이 메모리를 차지하게 된다.

---

출처 : Introduction to Algorithms 번역본 (Thomas H.Cormen등 지음, 문병로 등 옮김, 한빛아카데미)