슈트라센 알고리즘
알고리즘을 구현하는데에 효율성은 상당한 비중으로 고려해야 할 부분이다. 같은 수의 데이터를 얼마나 빠른 속도로 처리하는 것은 그 데이터의 개수가 늘어날 수록 결과는 천차만별일 수 있기 때문이다.
때문에 알고리즘을 구현할 때에는 빅오 표기법이 중요하다. Big O 표기법은 보통 알고리즘의 시간 복잡도와 공간 복잡도를 나타내는데 주로 사용된다고 한다.
슈트라센을 알기 전에 먼저 빅 오 (Big O) 에 대해 알 필요성을 느꼈다.
Big O표기법
O(1) < O(log n) < O(n) < O(nlog n) < O(n^2) < O(2^n)
- 왼쪽에서 오른쪽으로 갈수록 연산 속도가 느리다.
- (상수함수 < 로그함수 < 선형함수 < 다항함수 < 지수함수) 에 대응한다.
위 그림을 보면 알 수 있듯이, O(2^n) / O(n^2) 와 같이 지수형 증가를 가지고 있는 연산은 데이터 개수 가 증가함에따라 연산 시간 이 기하 급수적으로 증가한다. 때문에 Big O 내부의 값 f(n)을 줄이기 위해서는 n이외의 값들이 최대한 작은 값을 가지는게 유리하다.
이제부터 진짜! 슈트라센 알고리즘 에 대해 알아보겠다. 슈트라센 알고리즘은 폴커 슈트라센(Volker Strassen)이 1969년에 발견한 행렬 곱셈 알고리즘이다.
행렬곱 2X2 를 예시로 들어보자,
이때에 A,B 두 행렬곱 결과 행렬 C는 아래와 같은 계산을 거쳐 완성이 된다.
이처럼 총 8번의 곱셈이 필요하다
nXn 행렬곱으로 일반화 시켜보면 총 n^3번의 곱셈이 필요하다. 때문에 행렬곱을 O(n^3) 이라 표기 한다.
하지만 이는 지수형 증가를 보이기 때문에 n^k 에서 k를 최대한 작은 수로 설정 할 수 있다면 n이 커짐에 따라 그 계산의 효율성은 극명한 차이를 보일것이다.
폴커 슈트라센(Volker Strassen) 이 개발한 슈트라센 알고리즘은 행렬곱에서 이 k를 낮춘 첫 알고리즘인 것 같다.(아직까지 찾아본 바로는 그렇다.)
그럼 어떻게?
k 값을 낮추었을까?
분할 정복(Divide and Conquer) 전략을 썼다고 볼 수 있을 것 같다. (분할정복링크는 내용도 깔끔하고 시각적으로 정리를 잘 해놓은것 같은 블로그로 걸어두었다.)
이 M_k 행렬들은 C_ij행렬들을 표현하는데 쓰인단다.
전체 M_ij 행렬에서 곱셈 7번 / 덧셈18번 이 쓰였다. 기존 행렬곱에서 곱셈8번 / 덧셈4번이 쓰인것과 확연한 차이를 보인다.
사칙연산 계산 수가 더 많은데? 라고 생각하고 있었는데 찾아보니까 행렬곱에서 곱셈 연산시간이 덧셈 시간보다 더 많이든단다. 그래서 어느정도는 덧셈수가 늘어나더라도 곱셈 수를 줄이는게 시간적으로 더 효율적인가보다.
2X2 행렬곱은 이렇게 하면된다는 것을 알겠다. 그럼 nXn 으로 확장해서 생각해보아야 하는데 이 계산법을 어떻게 확장시킬까?
한참 고민하면서 이런저런 글을 읽어보다가 해답을 찾았다. 결국 분할 정복 을 빼먹고 생각하고 있었다. 슈트라센 알고리즘은 2^n꼴 형태 일때 가능한 것이었다. 2^n 꼴의 행렬을 2X2 행렬로 분할 하고 정복한 뒤 다시 합치면 되는거였다!
*
하지만 이 알고리즘 역시 문제가 있었다.
시간적 효율성 을 챙긴대신에 기존의 행렬곱 대비 수치 안정성이 떨어지는 문제점이 발생한다는 것이었다.
알고리즘을 구현할때에 데이터 종류, 형태 별로 적절한 메소드를 선택하는것도 중요함을 다시금 생각하게 되었다.
슈트라센이 대단하구나! 라는 생각을 하기 무섭게, 아래를 좀 더 읽어보니 이보다 시간면에서 효율적인 알고리즘들이 있었다. 이 포스팅은 슈트라센이 메인이기에 나머지는 짧게 소개만 하고 끝내려 한다.
- 위노그라드 알고리즘(Winograd algorithm) -1980년 곱셈7번 / 덧셈15번
- 빅터판이 개발한 알고리즘 - O(n^2.795)
- 코퍼스미스-위노그라드 알고리즘(Coppersmith–Winograd algorithm) - O(n^2.376)
- Stother가 개발한 알고리즘 - 2010년 O(n^2.3737)
- 월리엄스가 개발한 알고리즘 - 2011년 O(n^2.3727)
Leave a comment