Divide and Conquer - Matrix Multiplication / Karatsuba Algorithm

Matrix Multiplication

• n x n 행렬 두 개 곱셈 ⇒ 일반적인 방법으로는 O(n^3)

---

Apply Divide and Conquer

A는 4 x 4 행렬

|A B| |E F| = |AE + BG …
|C D| |G H| |CE + DG …

T(N) = 8T(N/2) : 8번의 곱셈 횟수
여전히 T(N) = O(N^3)

---

Strassen’s Algorithm

위에서 이어져서 아래와 같이 곱셈 1번 계산으로 압축 가능.
R = (A + D)(E + H)
S = (C + D)E T = A(F - H)
U = D(G - E) V = (A + B)H
W = (C - A)(E + F)
X = (B - D)(G + H)

AE + BG = R + H - V + X
AF + BH = T + V
CE + DG = S + U
CF + DH = R - S + T + W

⇒ T(N) = 7T(N/2) : 즉, 8번의 곱셈 횟수를 7번으로 압축
T(N) = O(2^log7N) = O(N^2.807…) < O(N^3)

---

Karatsuba Algorithm

• 행렬 말고 그냥 곱셈 → 일반적인 방법으로는 O(n^2)

두 수 x, y를 곱한다고 했을 때
x = x1b^m + x0
y = y1b^m + y0

ex) 238675, b=10 ⇒ 238*10^3 + 675

따라서
1. xy = x1y1b^2m + (x1y0 + y1x0)b^m + x0y0
2. x1y0 + y1x0 총 곱셈 횟수가 두 개.
아래와 같이 변경가능.
x1y0 + y1x0 = x1y0 + y1x0 + (x1y1 + x0y0) - (x1y1 + x0y0)
= x1(y0 + y1) + x0(y0 + y1) - x1y1 - x0y0
= (x1 + x0)(y0 + y1) - x1y1 - x0y0
x1y1, x0y0 는 1. 에서 이미 구한 값을 사용하면 되므로
(x1 + x0)(y0 + y1)만 계산하면 됨. 이것은 곱셈 횟수가 한번.
즉, 곱셈 횟수 2번을 → 곱셈 횟수 1번으로 압축.
⇒ O(n^log3)