[CLSR] 4.2 Strassen's algorithm for matrix multiplication(Ch 4. divide-and-conquer)(미완)

(구체적 슈트라센 알고리즘은 생략함)

---

정방행렬의 곱은 다음으로 일반화할 수 있다.

$A = (a_{ij})$이고 $B = (b_{ij})$인 $n \times n$행렬일 때,

$C = A \cdot B$의 원소 $c_{ij}$는 $i,j = 1,2, \cdots, n$에 대해 다음과 같이 나타낼 수 있다.

$$ c_{ij} = \sum_{k=1}^{n} a_{ik} \cdot b_{kj} $$

이를 단순한 방법으로 연산을 시키면 각 (for i = 1 to n) (for j = 1 to n)마다 (for k = 1 to n)번의 $a_{ik} \cdot b_{kj}$의 연산이 있어야 하므로, $\Theta(n^3)$의 시간이 소요된다.

언뜻 생각하기에는 $\Omega(3)$의 시간이 걸릴 것 같지만 $o(n^3)$이 걸릴 수 있는 방법이 존재한다.

Strassen의 알고리즘을 사용하면 $\Theta(n^{lg7})$의 시간으로 $n \times n$행렬의 곱을 계산할 수 있다.

$lg7$은 2.80과 2.81의 사이이므로 $O(n^{2.81})$이라고 할 수 있다.

---

A simple divide-and-conquer algorithm

편의상 $n$이 2의 멱수라고 가정한다.

각 divide 단계에서 $n \times n$행렬을 네 개의 $n/2 \times n/2$행렬로 나눈다(앞의 가정으로 $n/2$는 $n \geq 2$인 이상 항상 정수이다.).

$A$, $B$, $C$를 다음과 같이 $n/2 \times n/2$행렬 네 개로 partition할 수 있다.

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

그러면 $C = A \cdot B$는 다음과 같이 쓴다.
$C = \begin{pmatrix} {C_{11}} & {C_{12}} \\ {C_{21}} & {C_{22}} \\ \end{pmatrix} = \begin{pmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \\ \end{pmatrix} \cdot \begin{pmatrix} B_{11} & B_{12} \\ B_{21} & B_{22} \\ \end{pmatrix}$

각 부분 행렬은 다음과 같다.

$C_{11} = A_{11} \cdot B_{11} + A_{12} \cdot B_{21}$,

$C_{12} = A_{11} \cdot B_{12} + A_{12} \cdot B_{22}$,

$C_{21} = A_{21} \cdot B_{11} + A_{22} \cdot B_{21}$,

$C_{22} = A_{21} \cdot B_{12} + A_{22} \cdot B_{22}$.

 

알고리즘의 수도 코드는 다음과 같다.

square-matrix-multiply-recursive(A, B)
n = A.rows
let C be a new n * n matrix
if n == 1
	c_11 = a_11 * b_11
else partition A, B, and C as in texts.
	C_11 = square-matrix-multiply-recursive(A_11, B_11)
    		+ square-matrix-multiply-recursive(A_12, B21)
	C_12 = square-matrix-multiply-recursive(A_11, B_12)
    		+ square-matrix-multiply-recursive(A_12, B22)
	C_21 = square-matrix-multiply-recursive(A_21, B_11)
    		+ square-matrix-multiply-recursive(A_22, B21)
	C_22 = square-matrix-multiply-recursive(A_21, B_12)
    		+ square-matrix-multiply-recursive(A_22, B22)
return C

만약 파티셔닝 했을 때 새 행렬을 만들었으면 첫 단계에서만 $\Theta(n^2)$의 시간이 걸렸을 것이다.

하지만 배열에 인덱스를 통해 접근함으로써 파티셔닝 자체에 $\Theta(1)$의 시간만 걸릴 수 있다(점근적으로는 차이가 없긴 하다).

n = 1인 단계에서는 스칼라 곱셈 한 번만 시행하므로 $T(1) = \Theta(1)$이다.

n > 1인 단계에서는 재귀 호출을 8번씩 시행하는데 각 행렬 곱셈은 $n/2 \times n/2$의 크기이므로 $T(n/2)$가 걸린다.

따라서 재귀 호출에 $8T(n/2)$가 소요된다.

또한 재귀 호출이 끝난 후 행렬 원소들간의 덧셈에는 $\Theta(n^2)$의 시간이 소요된다.

이를 종합하면 다음과 같다.

$$\begin{equation} \begin{split} T(n) & = \Theta(1) + 8T(n/2) + \Theta(n^2) \\ &= 8T(n/2) + \Theta(n^2) \end{split} \end{equation}$$

모든 케이스를 종합하면 다음과 같다.

$$T(n) = \begin{cases} \Theta(1) & if\, \, n = 1, \\ 8T(n/2) + \Theta(n^2) & if \, \, n >1 \end{cases} $$

 

나중에 4.5에서 보겠지만 해를 구하면 $T(n) = \Theta(n^3)$으로 정의대로 계산하는 것과 차이가 없다.

---

Strassen's method

이 방법의 핵심은 8개의 재귀 호출을 7번만 하고 $n/2 \times n/2$행렬의 덧셈을 몇 번 더하는 것이다.

상수 개의 행렬 덧셈은 $\Theta$표기에서는 흡수되어 사라질 것이다.

1. $A$, $B$, $C$를 $n/2 \times n/2$의 행렬로 나누어라. 여기서는 $\Theta(1)$의 시간이 걸린다.
2. $n/2 \times n/2$사이즈의 행렬 열 개 $S_1, S_2, \cdots, S_{10}$를 만든다. 각 행렬은 1.의 행렬의 합이나 차분이다. 여기서는 $\Theta(n^2)$가 걸린다.
3. 2.에서의 행렬 열 개를 이용하여 재귀적으로 일곱 개의 행렬곱 $P_1 , P_2 \cdots, P_7$을 생성해라. 각 $P_i$는 $n/2 \times n/2$크기이다.
4. 각 $C_{11}, C_{12}, C_{21}, C_{22}$를 $P_i$행렬의 합과 차분의 조합으로 만들어라. 여기서는 $\Theta(n^2)$가 소요된다. 

결론적으로 $T(n) = \begin{cases} \Theta(1) & if\, n = 1, \\ 7T(n/2) + \Theta(n^2) & if \, n > 1. \end{cases} $의 시간이 걸리고 4.5의 방식으로 해를 구하면 $T(n) = \Theta(n^{lg7})$이 나온다.

자세한 방식은 책을 참조..