[알고리즘]strassen 스트라센 행렬 곱셈

[알고리즘]strassen 스트라센 행렬 곱셈

선형대수학에서 슈트라센 알고리즘은 폴커 슈트라센이 1969년에 개발한 행렬 곱셈 알고리즘이다.

일단 strassen 행렬 곱셈에 대해서 알아보면

알고리즘

A와 B를 체 F에 대한 정사각행렬이라고 하자. 두 행렬의 곱 C는 다음과 같다.

만약 A와 B가 2ⁿ × 2ⁿ 꼴의 크기가 아니라면 먼저 모자라는 행과 열을 0으로 채운다. 이 경우 행렬 곱셈이 끝난 뒤 행렬에서 필요한 부분만 다시 잘라 내야 한다.
이제 A, B, C를 같은 크기의 정사각행렬 네 개로 나눈다.
 

이 때,

따라서 다음이 성립한다.
 

 
 
이 과정에서는 필요한 연산의 수가 줄어 들지 않는다. 여전히 Ci, j 행렬을 계산하려면 여덟 번의 곱셈과 네 번의 덧셈이 필요하다.
이제 다음과 같은 행렬을 정의한다.
 

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

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

실제로는 n이 작을 경우 정의에 따라 행렬 곱셈을 하는 경우가 빠를 수도 있기 때문에, 보통 작은 n에 대해서는 일반적인 방법으로 곱셈을 하도록 구현한다.슈트라센 알고리즘은 속도에 비해 수치 안정성이 떨어지는 것으로 알려져 있다.

두 행렬 A와 B를 곱한 결과를 C라 할 때, 실제 오차인 는 보다 작음이 알려져 있다. 이는 일반적인 행렬 곱셈보다 더 큰 오차이다.

출처 - http://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

strassen 행렬 곱셈을 사용하는 이유는 행렬곱셈의 수행시간단축이다.

제가 알고리즘을 공부할때 사용했던 교재입니다.

개인적으로 평점이 정확하다고 알려드리고싶습니다...ㅋㅋㅋ

발표했던 ppt의 내용입니다. 그당시 최대한 이해하기 쉽게 만들었습니다.

여러 자료들을 참고해가며 열심히 구현했던 소스입니다.

로직자체는 맞는것 같은데....

결과적으로는 실패하였습니다.

그럼 이걸 왜올려???
그렇습니다. 실패한게 포스팅의 목적입니다.ㅋㅋㅋㅋㅈㅅ

실패의 원인은 구현 당시 사용자가 입력한 행렬의 크기에 맞게 동적할당을 하도록 구현하기 때문인듯/?

행렬곱셉의 수행시간에 동적할당을 받는 시간까지 추가되었기 때문에

아래와 같이 행렬의 크기가 커짐에 따라 속도도 늘어나게 되었습니다.

엄청난 수행시간입니다.

관련자료가 많지 않아 구현당시에는 처리를 못하고 발표를 했습니다...ㅜㅜ

다행히 실패한 결과값을 더 좋아라 해주셨던 교수님덕분에 잘 넘어갔지만

이 글을 찾아보시는 분들은 같은 실수가 없길 바라며,

이분의 글이 가장 잘 표현된 글같아 추천 합니다.

http://partyjoy2001.blog.me/120094528073

첨부파일에 있는 문서가 공부하시는데 많은 도움이 되실겁니다.