[분할과 정복] Strassen algorithm

행렬 곱셈

 

정사각 행렬 A, B를 가지고 곱셈을 한다고 생각해보자.

 

행렬곱 C = AB는 다음과 함께 정의된다.

 

이 때 i = 1, ... ,m, j = 1, ..., p에 대해 C의 성분은 다음과 같이 정의된다. 

 

이는 곧 A의 i번째 행과 B의 j번째 열의 성분들을 각각 곱해 더한 것과 같은데, A의 i번째 행과 B의 j번째 열의 스칼라곱인 것이다.

 

그런고로 AB는 다음과 같이 쓸 수도 있다.

 

 

3중 반복문이 행렬의 크기 n만큼 돌기 때문에 n x n 크기의 두 행렬을 곱하면 O(n^3) 의 시간이 소요된다.

 

 

줄이는 방법이 없을까?

 

 

Strassen algorithm (슈트라센 알고리즘)

 

행렬의 덧셈이 곱셈보다 더 빠른 점을 이용하기 위해 쪼갠 행렬들의 곱셈 횟수를 줄이고 덧셈 횟수를 늘린다.

 

곱셈은 $ n^3 $ 이지만 행렬간의 덧셈은 $ n^2 $ 만에 가능하기 때문이다.

 

$$ C = AB , A, B, C \in F^{2^n \times 2^n} $$ 

 

만약 A와 B가 $ 2^n \times 2^n $ 꼴의 크기가 아니라면 먼저 모자라는 행과 열을 0으로 채운다. 이 경우 행렬 곱셈이 끝난 뒤 행렬에서 필요한 부분만 다시 잘라내야 한다.

 

이제 A, B, C를 같은 크기의 정사각행렬 네 개로 나눈다.

 

이 때, 

 

$$ A_{i, j}, B_{i, j}, C_{i, j} \in F^{2^n \times 2^n} $$ 

 

따라서 다음이 성립한다.

 

$$ \\ C_{1,1} = A_{1,1}B_{1,1} + A_{1,2}B_{2,1}
\\ C_{1,2} = A_{1,1}B_{1,2} + A_{1,2}B_{2,2}
\\ C_{2,1} = A_{2,1}B_{1,1} + A_{2,2}B_{2,1}
\\ C_{2,2} = A_{2,1}B_{1,2} + A_{1,2}B_{2,2} $$

 

 

이 과정에서는 필요한 연산의 수가 줄어들지 않는다. 여전히 $C_{i,j} $ 행렬을 계산하려면 여덟번의 곱셈과 네번의 덧셈이 필요하다.

 

이제 다음과 같은 행렬을 정의한다.

 

 

 

이 $M_k$ 행렬들은 $C_{i,j}$ 행렬을 표현하는 데 쓰이는데, 이 행렬들을 계산하는 데는 일곱 번의 곱셈(각 변수마다 한 번씩) 과 10번의 덧셈이 필요하다. 이제 $C_{i,j}$행렬은 다음과 같이 표현할 수 있다.

 

이 과정에서는 곱셈이 사용되지 않기 때문에, 전체 곱셈을 일곱 번의 곱셈과 18번의 덧셈으로 처리할 수 있다. 큰 행렬에 대해서는 행렬의 곱셈이 덧셈보다 더 많은 시간을 필요로 하기 때문에 덧셈을 더하는 대신 곱셈을 덜 하는 것이 전체적으로 더 효율적이다.

 

이 과정을 재귀적으로 반복할 경우 총 $ {\displaystyle 7\cdot n^{\log _{2}7}-6\cdot n^{2}} $ 번의 연산이 필요하다.

$ {\displaystyle \log _{2}7=2.807\cdots } $ 이므로 전체 수행 시간은 약 $ O(n^{2.807}) $이다.

 

 

실제로는 n이 작을 경우 정의에 따라 행렬 곱셈을 하는 경우가 빠를 수도 있기 때문에, 보통 작은 n에 대해서는 일반적인 방법으로 곱셈을 하도록 구현한다.

 

- Starssen Algorithm은 재귀적으로 돌려 시간이 오래 걸리며, 반복적 알고리즘으로 바꾸는 데 어렵다. 

- $M_1 $ ~ $M_7$ 을 담아둘 자리를 기억장치 안에 마련해야 하므로, 행렬이 클 경우 자리를 너무 많이 차지한다.

 

참고

https://ko.wikipedia.org/wiki/%EC%8A%88%ED%8A%B8%EB%9D%BC%EC%84%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

슈트라센 알고리즘 - 위키백과, 우리 모두의 백과사전

https://m.blog.naver.com/babobigi/220502327816