[ Divide and Conquer ] Matrix Multiplication & Karatsuba Algorithm

Matrix Multiplication

• Multiply 2 N by N Matrices
• Takes O(\(N^3\)) Time using Normal Method -> Let's consider only number multiplication

Apply Divide and Conquer

지금 A, B, C, D 이것들이 전부 N/2 by N/2 Matrix 들이다.

이러한 행렬들을 위의 공식으로 계산하면 결국 N by N 행렬을 곱한 것과 같다.

결국 이는 O(N^3)이다.

 

Strassen's Algorithm

곱하기 갯수에 집중해서 생각해보자

곱하기가 7번뿐이다. 대신 덧셈과 뺄셈이 늘어났다

곱셈이 줄어들기 때문에, O(2^log7N)이 된다. 

 

Karatsuba Algorithm 

n x n 자리수를 곱하는 것

O(n^2) 시간이 걸린다. 

 

자리수를 divide and concur 하자

n = 2m 이라면, \(x \times y = (x_1 10^m + x_0) (y_1 10^m + y_0)\)