알고리즘: 슈트라센(Strassen) 행렬 곱셈 알고리즘 (feat.c++ ,pseudocode)

이번 포스팅은 일반적인 정방행렬의 곱셈을 알아보고 

더 빠른 슈트라센(Strassen) 행렬곱셈에 대해서 알아본다.

 

< 일반적인 행렬의 곱셈 >

void matrixMulti(const int a[][N], const int b[][N], int c[][N]) {

	for (int i = 0; i < N;i++)
		for (int j = 0; j < N; j++)
		{
			c[i][j] = 0;
			for (int k = 0; k < N; k++) {
				c[i][j] = c[i][j] + a[i][k] * b[k][j];
			}
		}
}

일반적인 행렬곱셈은 우리가 아는 행렬곱셈 그대로 코딩하면

위와 같은 3중 for문으로 구성된다.

 

 

1. 시간복잡도 분석

 

입력 크기 행과 열의 수가 n이라고 할 때

 

1) 곱셈의 관점

 

2) 덧셈의 관점

 

결론적으로 다음과 같은 시간복잡도를 갖는다. 

 

 

 

 

 

하지만 이를 더 줄여 볼 수 없을까?

 

그래서 쉬트라쎈(Strassen)의 방법을 사용한다.

 

 

2 x 2 matrix를 예로 들어보자

 

C = A x B 라고 한다면 

 

쉬트라쎈 방법을 이용하면 다음과 같이 표현된다. 

 

일반적인 행렬 곱셈 방식을 사용한다면 곱셈 8번, 덧셈 4번이 필요한 반면,

쉬트라쎈의 방법을 이용하면 곱셈 7번, 덧셈/뺄셈 18번을 필요로 한다. 

 

언뜻 보면, 원래의 방식이 더 좋아 보이는데, 행렬의 크기가 커지면 

쉬트라쎈 방법의 진가가 드러난다. 

 

 

 

< 슈트라센 행렬곱셈의 수도 코드 >

void strassen(int n, n*n_matrix A, n*n_matrix B, n*n_matrix &C){

if( n <= 임계값 )
  단순한 알고리즘을 사용하여 C = A * B;
else{
 A를 4개의 부분행렬로 분할;
 B를 4개의 부분행렬로 분할;
 쉬트라쎈의 방법을 사용해서 C = A * B를 계산;
 //recursion호출이용

}
}

 

여기서 임계값은 단순한 알고리즘보다 쉬트라쎈 알고리즘을 사용하면 더 좋을 것이라고 예상되는 지점을 의미

 

 

 

 

 

< 시간복잡도 분석 1(곱셈만 생각하는 경우) > 

 

입력크기가 n이고 임계값을 1이라고 하자 (임계값은 차수에 전혀 영향을 미치지 않는다)

 

재현식은 다음과 같다. (입력의 크기가 절반으로 줄면서 곱셈이 7번 있으므로)

 

이 식을 전개하면

위과 같아지고 일반적인 행렬 곱셈 알고리즘보다 더 좋은 시간복잡도를 갖는다. 

 

 

 

 

 

< 시간복잡도 분석 2 >

 

이번에는 도사정리를 이용해서 해를 구해본다.

 

위에서와 마찬가지로 임계값을 1이라고 할때, 재현식은 다음과 같다.

(입력의 크기가 절반씩 줄면서 곱셈이 7번, 덧셈 18번 있으므로)

 

 

여기서 도사정리를 이용하면 

위와 같음을 알 수 있다.