Matrix Multiplication

• Multiply 2 N-by-N matrices
• Takes O(N^3) time using normal method
  • let’s consider only number multiplications
  • 입력이 N^2개이고 원소 하나를 계산하는데 N번의 곱셈을 해야 함
• Can we do it faster?

생각해보면 서로 곱하기 연산을 하지 않는 값들이 존재한다. 예를 들어 왼쪽 행렬의 2와 오른쪽 행렬의 7은 서로 곱해지지 않는다. 그래서 O(N^3)보다 빠르게 해결할 수 있다고 생각되지 않는다.

| 1 2 3 |   | 3 3 4 |
| 3 4 5 | X | 2 4 6 |
| 1 4 5 |   | 1 3 7 |

그러나 놀랍게도 O(N^3)보다 빠른 시간에 풀 수 있는 방법이 있다. 그리고 그 방법은 divide and conquer를 사용한다.

Apply Divide and Conquer

| A B |   | E F |     | AE+BG AF+BH |
|     | X |     |  =  |             |
| C D |   | G H |     | CE+DG CF+CH |

여기서 A~H는 상수가 아닌 전체 행렬의 부분 행렬이다. Idea: N X N 행렬을 2*2가 되도록 partition해 재귀적으로 구해보자.

그러나 이 방법은 그냥 계산하는 것보다 느리다. 재귀도 돌리고 배열도 만들고 등등해서 느림.

시간복잡도를 계산해보자.

T(N) 
= 8 * T(N/2) 
= (8^2) * T(N/(2^2))
= (8^3) * T(N/(2^3))
= ... 
= (8^logN) * T(N/(2^logN)) = (8^logN) * T(1)= 8^logN = N^log8 = N^3

2를 logN번 곱하면 N이 되므로 위 과정을 logN번 반복한다. 8도 logN번 곱해지므로 계산하면 N^3이 된다.

Strassen’s Algorithm

| A B |   | E F |     | AE+BG AF+BH |
|     | X |     |  =  |             |
| C D |   | G H |     | CE+DG CF+CH |

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)

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

위 행렬을 계산해보자. 2X2 행렬이므로 정석적인 방법으로 계산하면 곱하기 연산을 8번 해야 한다.

R, S, …, X를 위와 같이 정의해 행렬곱의 각 원소를 R, S, …, X로 표현해보자. R, S, …, X는 각각 곱하기 연산 한 번으로 계산할 수 있으므로(곱하기만 세기로 했음), 곱하기 연산 7번 만에 행렬곱을 구할 수 있다.

Time Complexity

T(N) 
= 7 * T(N/2) 
= (7^2) * T(N/(2^2))
= (7^3) * T(N/(2^3))
= ... 
= (7^logN) * T(N/(2^logN)) = (7^logN) * T(1)= 7^logN = N^log7 = N^(2.807...)

구현해서 쓰면 진짜 더 빠르다. matrix들의 크기가 N^2이고 출력 size가 N^2이기 때문에 N^2보다는 느리다. 하지만 N^3보다는 확실히 빠르다.

N^2 < N^log7 < N^3

근데 더 놀랍게도 N^log7보다도 더 빠르게(물론 N^2보단 느림) 행렬곱을 구할 수 있는 방법이 발견되었다!

Multiplying matrices in O(n 2.373) time (2014, O(n 2.373))

Matrix Multiplication via Arithmetic Progressions (1990, O(2.376))

세상에 이렇게 열심히 사는 사람도 있다.