Matrix multiplication 행렬의 곱셈

Explain

• 행렬의 곱셈 알고리즘에 대해서 정리
• 행렬의 곱셈 알고리즘에는 여러 가지 방식이 존재한다 이 중에서도 단순한(Iterative, Divide and Conquer) 알고리즘과 스트라센(strassen) 두 알고리즘의 차이점을 비교.
• 단순한 방식(Iterative) 의 알고리즘의 대부분은 \(\Theta(n^3) \)의 시간의 시간 복잡도를 가진다.
• 이외에도 Pan, Bini, CW, SW 방식 등의 다양한 알고리즘이 존재한다.
• 두개의 정사각형[n*n] 행렬의 곱은 \( 2n^2 \) 의 원소를 가지므로 두 행렬의 곱은 \( \Omega(n^2) \) 이다.

Iterative Algorithm

• C = AB, n * m 크기의 행렬 A와 m * p 크기의 행렬 B가 있을때 행렬 C 는  n * p의 크기를 가진다.
• 행렬 A, B의 곱연산을 아래와같은 수식으로 표현할수있다.

$$C_{ij} = \sum_{k=1}^{m}a_{ik}b_{kj}$$

위 내용을 토대로 아래와 같은 알고리즘을 작성 할 수 있다.

입력 : 행렬 A [ n * m ] , 향렬 B [ m * p ]

결과값을 저장 할 n * p의 크기를 가지는 행렬 C 생성.

For i from 1 to n :

For j from 1 to p :

    sum = 0

    For k from 1 to m:

        Set sum  \( \leftarrow \) sum + \( A_{ik} * B_{kj} \)

          Set \( C_{ij} \leftarrow \) sum

Return \(C\)

• 위 알고리즘은 \(\Theta(npm)\)의 시간 복잡도를 가지는 것을 알 수 있다. 일반적으로 알고리즘 분석에는 정사각형의 행렬[n*n]이 사용되니 해당 알고리즘은 \(\Theta(n^3)\) 의 시간 복잡도를 가진다고 볼 수 있다.

Divide and conquer Algorithm

• \(2^n\) 크기를 가지는 동일한 행렬 A,B의 곱셈에 대해 아래와 같은 수식이 성립한다.

$$\begin{pmatrix}C_{11} & C_{12} \\C_{21} & C_{22}\end{pmatrix} = \begin{pmatrix}A_{11} & A_{12} \\A_{21} &A_{22}\end{pmatrix} = \begin{pmatrix}B_{11} & B_{12} \\B_{21} & B_{22}\end{pmatrix} = \begin{pmatrix}A_{11}B_{11} + A_{12}B_{21} & A_{11}B_{12} + A_{12}B_{22}\\A_{21}B_{11} + A_{22}B_{21} & A_{21}B_{12} + A_{22}B_{22}\end{pmatrix}$$

• 위 수식에서 8개의 \( \frac{n}{2} \) 크기의 부분 행렬의 곱과 그들의 합\(\Theta(n^2)\)으로 이뤄진다는 것을 알 수 있다.
• 이때 위 알고리즘의 시간 복잡도는 아래와 같다. ( n 은 1이 아닌 경우 반복된다. )

$$T(n) = \begin{cases} \Theta(1)  & \text{if $n$ is 1} \\[2ex] 8T(\frac{n}{2}) + \Theta(n^2) & \text{if $n$ > 1}\end{cases}$$

• 위 수식은 Application of master theorem 으로 풀면 \( \Theta(n^3) \) 의 시간 복잡도를 가지므로 Iterative 알고리즘과 동일한 시간 복잡도를 가진다는 것을 알 수 있다.

Strassen Algorithm

• 선형 대수학에서 Strassen Algorithm 이란 행렬의 곱을 위한 알고리즘 중 하나이다.
• 크기가 큰 행렬에 대해 기본적인 알고리즘 보다 유용하고 빠르다. 하지만 제일 빠른 알고리즘은 아니라는것을 참고.
• Strassen algorithm은 아래의 7개의 수식의 정의를 기본으로 한다.
$$\begin{align}M_1 & := (A_{1,1}+A_{1,2})(B_{1,1}+B_{2,2})\\ M_2 & := (A_{2,1}+A_{2,2})B_{1,1}\\ M_3 & := A_{1,1}(B_{1,2}-B_{2,2})\\ M_4 & := A_{2,2}(B_{1,2} - B_{2,2})\\ M_5 & := (A_{1,1} + A{1,2})B_{2,2}\\ M_6 & := (A_{2,1} - A_{1,1})(B_{1,1} + B_{1,2})\\ M_7 & := (A_{1,2} - A_{2,2})(B_{2,1} + B_{2,2})\end{align}$$
• 기본적인 알고리즘의 진행시 8번의 곱셈 연산이 일어나는 반면 위 알고리즘으로 진행시 7번의 곱셈 연산이 일어나는것을 알수있다.
• 이때 행렬 A,B의 곱셈 연산의 결과 행렬 C 는 아래와 같다.

$$\begin{align}C_{1,1} & = M_1 + M_4 - M_5 + M_7\\ C_{1,2} & = M_3 + M_5\\ C_{2,1} & = M_2 + M_4\\ C_{2,2} & = M_1 - M_2 + M_3 + M_6\end{align}$$

• \( \mathscr{C} \) 가 덧셈 연산의 횟수라고 가정했을때 \( f(n) = 7f(n-1) + \mathscr{C}4^n \) 의 복잡도를 보여주는것을 알 수 있으며, 그러므로 \( N = 2^n \) 일때 \( f(n) = (7 + o(1))^n \) 복잡도를 보여주는것을 알 수 있다. 이를 Big O 표기법으로 나타내면 아래와 같다.

$$O([7+o(1)]^n = O(N^{log2 \ 7+o(1)}) \approx O(N^{2.8074}) $$

• 일반 적인 행렬의 곱 알고리즘의 시간 복잡도인 \( \Theta(n^3) \) 의보다 대부분의 경우 빠르다고 할수 있다. 하지만 Stranssen Algorithm 의경우 일반적인 알고리즘보다 더많은 memory store를 요구하는 등의 단점을 가지므로 optimal 하지는 않다. 현재는 Stranssen 단점을 보완한 알고리즘(?) 과 CW, SW 알고리즘등의 여러가지 부분에서 뛰어난 알고리즘이 많이 알려져있으므로 참고하자.

Reference

• Wiki - Matrix multipilication
• Wiki - Strassen algorithm