당신은 주제를 찾고 있습니까 “스트라 센 알고리즘 – [알고리즘 실습] 제3강 분할정복: Part 2-1. 쉬트라쎈 행렬 곱셈“? 다음 카테고리의 웹사이트 th.taphoamini.com 에서 귀하의 모든 질문에 답변해 드립니다: https://th.taphoamini.com/wiki/. 바로 아래에서 답을 찾을 수 있습니다. 작성자 주니온TV 아무거나연구소 이(가) 작성한 기사에는 조회수 1,365회 및 좋아요 15개 개의 좋아요가 있습니다.
Table of Contents
스트라 센 알고리즘 주제에 대한 동영상 보기
여기에서 이 주제에 대한 비디오를 시청하십시오. 주의 깊게 살펴보고 읽고 있는 내용에 대한 피드백을 제공하세요!
d여기에서 [알고리즘 실습] 제3강 분할정복: Part 2-1. 쉬트라쎈 행렬 곱셈 – 스트라 센 알고리즘 주제에 대한 세부정보를 참조하세요
경북대학교 컴퓨터학부 글로벌소프트웨어융합전공
알고리즘실습 2020년 1학기 3주차 강의
Foundations of Algorithms 5th Ed., Richard E. Neapolitan.
Chapter 2. Divide and Conquer.
2.5. Strassen Matrix Multiplication.
주니온TV@유튜브 – 알고리즘으로 이해하는 초연결 세상
https://www.youtube.com/channel/UCOcPzXDWSrnaKXse9XOPiog
스트라 센 알고리즘 주제에 대한 자세한 내용은 여기를 참조하세요.
슈트라센 알고리즘 – 위키백과, 우리 모두의 백과사전
선형대수학에서 슈트라센 알고리즘은 독일의 수학자 폴커 슈트라센(Volker Strassen)이 1969년에 개발한 행렬 곱셈 알고리즘이다. 정의에 따라 n×n 크기의 두 행렬을 …
Source: ko.wikipedia.org
Date Published: 2/8/2021
View: 4942
Strassen Algorithm – Samsung Software Membership
안녕하세요? 오늘은 행렬을 효율적으로 곱하는 방법과, 그 방법 중 하나이자 분할 정복의 대표적인 예시인 슈트라센 알고리즘(Strassen Algorithm)과 …
Source: www.secmem.org
Date Published: 7/8/2021
View: 7114
[분할 정복] Strassen algorithm – 이즈미르의 프로그래밍
분할 정복 알고리즘(Dive and conquer algorithm) 중에 하나인 Strassen을 알아보자. 중고등학생 때 행렬의 곱셈에 대해 배웠을 것이다.
Source: izmirprogramming.tistory.com
Date Published: 2/8/2021
View: 3142
슈트라센(Strassen) 행렬 곱셈 알고리즘 (feat.c++ ,pseudocode)
이번 포스팅은 일반적인 정방행렬의 곱셈을 알아보고 더 빠른 슈트라센(Strassen) 행렬곱셈에 대해서 알아본다. < 일반적인 행렬의 곱셈 > vo …
Source: seungjuitmemo.tistory.com
Date Published: 5/7/2021
View: 9608
슈트라센 알고리즘 증명 – 생새우초밥집
Proof of strassen algorithm … 슈트라센이 태어나기 전까진 말이다. … 이 알고리즘의 개발로 인해서 행렬 계산에 쓰였을 자원들을 조금이나마, 아니 엄청나게 …
Source: freshrimpsushi.github.io
Date Published: 7/3/2022
View: 6189
‘슈트라센 알고리즘’ 쉬운 설명 – 미닛
슈트라센 알고리즘은 독일의 수학자 폴커 슈트라센(Volker Strassen)이 1969년에 개발한 행렬 곱셈 알고리즘이다. 정의에 따라 ‘n’×’n’ 크기의 두 행렬을 곱하면 O(n) …
Source: ko.meaniit.com
Date Published: 7/25/2022
View: 9573
Python: 행렬 곱셈 알고리즘 소개
슈트라센 알고리즘을 이용하면 O(n^2.81) 정도의 시간 복잡도를 갖게 된다. (재귀). 즉, 7번의 곱셈과 18번의 덧셈/뺄셈 으로 행렬 곱셈을 하는 방법 …
Source: choiseokwon.tistory.com
Date Published: 2/13/2021
View: 6116
주제와 관련된 이미지 스트라 센 알고리즘
주제와 관련된 더 많은 사진을 참조하십시오 [알고리즘 실습] 제3강 분할정복: Part 2-1. 쉬트라쎈 행렬 곱셈. 댓글에서 더 많은 관련 이미지를 보거나 필요한 경우 더 많은 관련 기사를 볼 수 있습니다.
![[알고리즘 실습] 제3강 분할정복: Part 2-1. 쉬트라쎈 행렬 곱셈](https://i.ytimg.com/vi/V311C8o0W9I/maxresdefault.jpg)
주제에 대한 기사 평가 스트라 센 알고리즘
- Author: 주니온TV 아무거나연구소
- Views: 조회수 1,365회
- Likes: 좋아요 15개
- Date Published: 2020. 3. 28.
- Video Url link: https://www.youtube.com/watch?v=V311C8o0W9I
위키백과, 우리 모두의 백과사전
선형대수학에서 슈트라센 알고리즘은 독일의 수학자 폴커 슈트라센(Volker Strassen)이 1969년에 개발한 행렬 곱셈 알고리즘이다. 정의에 따라 n×n 크기의 두 행렬을 곱하면 O(n3)의 시간이 소요되지만 이 알고리즘은 대략 O(n2.38)의 시간이 소요된다.
알고리즘 [ 편집 ]
A와 B를 체 F에 대한 정사각행렬이라고 하자. 두 행렬의 곱 C는 다음과 같다.
C = A B A , B , C ∈ F 2 n × 2 n {\displaystyle \mathbf {C} =\mathbf {A} \mathbf {B} \qquad \mathbf {A} ,\mathbf {B} ,\mathbf {C} \in F^{2^{n}\times 2^{n}}}
만약 A와 B가 2n × 2n 꼴의 크기가 아니라면 먼저 모자라는 행과 열을 0으로 채운다. 이 경우 행렬 곱셈이 끝난 뒤 행렬에서 필요한 부분만 다시 잘라 내야 한다.
이제 A, B, C를 같은 크기의 정사각행렬 네 개로 나눈다.
A = [ A 1 , 1 A 1 , 2 A 2 , 1 A 2 , 2 ] , B = [ B 1 , 1 B 1 , 2 B 2 , 1 B 2 , 2 ] , C = [ C 1 , 1 C 1 , 2 C 2 , 1 C 2 , 2 ] {\displaystyle \mathbf {A} ={\begin{bmatrix}\mathbf {A} _{1,1}&\mathbf {A} _{1,2}\\\mathbf {A} _{2,1}&\mathbf {A} _{2,2}\end{bmatrix}}{\mbox{ , }}\mathbf {B} ={\begin{bmatrix}\mathbf {B} _{1,1}&\mathbf {B} _{1,2}\\\mathbf {B} _{2,1}&\mathbf {B} _{2,2}\end{bmatrix}}{\mbox{ , }}\mathbf {C} ={\begin{bmatrix}\mathbf {C} _{1,1}&\mathbf {C} _{1,2}\\\mathbf {C} _{2,1}&\mathbf {C} _{2,2}\end{bmatrix}}}
이 때,
A i , j , B i , j , C i , j ∈ F 2 n − 1 × 2 n − 1 {\displaystyle \mathbf {A} _{i,j},\mathbf {B} _{i,j},\mathbf {C} _{i,j}\in F^{2^{n-1}\times 2^{n-1}}}
따라서 다음이 성립한다.
C 1 , 1 = A 1 , 1 B 1 , 1 + A 1 , 2 B 2 , 1 {\displaystyle \mathbf {C} _{1,1}=\mathbf {A} _{1,1}\mathbf {B} _{1,1}+\mathbf {A} _{1,2}\mathbf {B} _{2,1}} C 1 , 2 = A 1 , 1 B 1 , 2 + A 1 , 2 B 2 , 2 {\displaystyle \mathbf {C} _{1,2}=\mathbf {A} _{1,1}\mathbf {B} _{1,2}+\mathbf {A} _{1,2}\mathbf {B} _{2,2}} C 2 , 1 = A 2 , 1 B 1 , 1 + A 2 , 2 B 2 , 1 {\displaystyle \mathbf {C} _{2,1}=\mathbf {A} _{2,1}\mathbf {B} _{1,1}+\mathbf {A} _{2,2}\mathbf {B} _{2,1}} C 2 , 2 = A 2 , 1 B 1 , 2 + A 2 , 2 B 2 , 2 {\displaystyle \mathbf {C} _{2,2}=\mathbf {A} _{2,1}\mathbf {B} _{1,2}+\mathbf {A} _{2,2}\mathbf {B} _{2,2}}
이 과정에서는 필요한 연산의 수가 줄어 들지 않는다. 여전히 C i,j 행렬을 계산하려면 여덟 번의 곱셈과 네 번의 덧셈이 필요하다.
이제 다음과 같은 행렬을 정의한다.
M 1 := ( A 1 , 1 + A 2 , 2 ) ( B 1 , 1 + B 2 , 2 ) {\displaystyle \mathbf {M} _{1}:=(\mathbf {A} _{1,1}+\mathbf {A} _{2,2})(\mathbf {B} _{1,1}+\mathbf {B} _{2,2})} M 2 := ( A 2 , 1 + A 2 , 2 ) B 1 , 1 {\displaystyle \mathbf {M} _{2}:=(\mathbf {A} _{2,1}+\mathbf {A} _{2,2})\mathbf {B} _{1,1}} M 3 := A 1 , 1 ( B 1 , 2 − B 2 , 2 ) {\displaystyle \mathbf {M} _{3}:=\mathbf {A} _{1,1}(\mathbf {B} _{1,2}-\mathbf {B} _{2,2})} M 4 := A 2 , 2 ( B 2 , 1 − B 1 , 1 ) {\displaystyle \mathbf {M} _{4}:=\mathbf {A} _{2,2}(\mathbf {B} _{2,1}-\mathbf {B} _{1,1})} M 5 := ( A 1 , 1 + A 1 , 2 ) B 2 , 2 {\displaystyle \mathbf {M} _{5}:=(\mathbf {A} _{1,1}+\mathbf {A} _{1,2})\mathbf {B} _{2,2}} M 6 := ( A 2 , 1 − A 1 , 1 ) ( B 1 , 1 + B 1 , 2 ) {\displaystyle \mathbf {M} _{6}:=(\mathbf {A} _{2,1}-\mathbf {A} _{1,1})(\mathbf {B} _{1,1}+\mathbf {B} _{1,2})} M 7 := ( A 1 , 2 − A 2 , 2 ) ( B 2 , 1 + B 2 , 2 ) {\displaystyle \mathbf {M} _{7}:=(\mathbf {A} _{1,2}-\mathbf {A} _{2,2})(\mathbf {B} _{2,1}+\mathbf {B} _{2,2})}
이 M k 행렬들은 C i,j 행렬을 표현하는 데 쓰이는데, 이 행렬들을 계산하는 데는 일곱 번의 곱셈(각 변수마다 한 번씩)과 10번의 덧셈이 필요하다. 이제 C i,j 행렬은 다음과 같이 표현할 수 있다.
C 1 , 1 = M 1 + M 4 − M 5 + M 7 {\displaystyle \mathbf {C} _{1,1}=\mathbf {M} _{1}+\mathbf {M} _{4}-\mathbf {M} _{5}+\mathbf {M} _{7}} C 1 , 2 = M 3 + M 5 {\displaystyle \mathbf {C} _{1,2}=\mathbf {M} _{3}+\mathbf {M} _{5}} C 2 , 1 = M 2 + M 4 {\displaystyle \mathbf {C} _{2,1}=\mathbf {M} _{2}+\mathbf {M} _{4}} C 2 , 2 = M 1 − M 2 + M 3 + M 6 {\displaystyle \mathbf {C} _{2,2}=\mathbf {M} _{1}-\mathbf {M} _{2}+\mathbf {M} _{3}+\mathbf {M} _{6}}
이 과정에서는 곱셈이 사용되지 않기 때문에, 전체 곱셈을 일곱 번의 곱셈과 18번의 덧셈으로 처리할 수 있다. 큰 행렬에 대해서는 행렬의 곱셈이 덧셈보다 더 많은 시간을 필요로 하기 때문에 덧셈을 더 하는 대신 곱셈을 덜 하는 것이 전체적으로 더 효율적이다.
이 과정을 재귀적으로 반복할 경우 총 7 ⋅ n log 2 7 − 6 ⋅ n 2 {\displaystyle 7\cdot n^{\log _{2}7}-6\cdot n^{2}} 번의 연산이 필요하다. log 2 7 = 2.807 ⋯ {\displaystyle \log _{2}7=2.807\cdots } 이므로 전체 수행 시간은 약 O(n2.807)이다. 실제로는 n이 작을 경우 정의에 따라 행렬 곱셈을 하는 경우가 빠를 수도 있기 때문에, 보통 작은 n에 대해서는 일반적인 방법으로 곱셈을 하도록 구현한다.
슈트라센 알고리즘은 속도에 비해 수치 안정성이 떨어지는 것으로 알려져 있다. 두 행렬 A와 B를 곱한 결과를 C라 할 때, 실제 오차인 ‖ C − A B ‖ {\displaystyle \lVert C-AB\rVert } 는 27 n 2 u ‖ A ‖ ‖ B ‖ + O ( u 2 ) {\displaystyle 27n^{2}u\lVert A\rVert \lVert B\rVert +O(u^{2})} 보다 작음이 알려져 있다. 이는 일반적인 행렬 곱셈보다 더 큰 오차이다.[1]
변형된 알고리즘 [ 편집 ]
슈무엘 위노그라드(Shmuel Winograd)는 1980년에 슈트라센 알고리즘을 변형한 위노그라드 알고리즘(Winograd algorithm)을 개발하였다. 이 알고리즘은 점근적으로 슈트라센 알고리즘과 동일한 복잡도를 지니지만 덧셈의 횟수를 15번으로 줄인 방법이다. 이 방법에서는 다음과 같은 변수를 쓴다.
S 1 = A 21 + A 22 {\displaystyle \mathbf {S} _{1}=\mathbf {A} _{21}+\mathbf {A} _{22}} S 2 = S 1 − A 11 {\displaystyle \mathbf {S} _{2}=\mathbf {S} _{1}-\mathbf {A} _{11}} S 3 = B 12 − B 11 {\displaystyle \mathbf {S} _{3}=\mathbf {B} _{12}-\mathbf {B} _{11}} S 4 = B 22 − S 3 {\displaystyle \mathbf {S} _{4}=\mathbf {B} _{22}-\mathbf {S} _{3}} M 1 = S 2 S 4 {\displaystyle \mathbf {M} _{1}=\mathbf {S} _{2}\mathbf {S} _{4}} M 2 = A 11 B 11 {\displaystyle \mathbf {M} _{2}=\mathbf {A} _{11}\mathbf {B} _{11}} M 3 = A 12 B 21 {\displaystyle \mathbf {M} _{3}=\mathbf {A} _{12}\mathbf {B} _{21}} M 4 = ( A 11 − A 21 ) ( B 22 − B 12 ) {\displaystyle \mathbf {M} _{4}=(\mathbf {A} _{11}-\mathbf {A} _{21})(\mathbf {B} _{22}-\mathbf {B} _{12})} M 5 = S 1 S 3 {\displaystyle \mathbf {M} _{5}=\mathbf {S} _{1}\mathbf {S} _{3}} M 6 = ( A 12 − S 2 ) B 22 {\displaystyle \mathbf {M} _{6}=(\mathbf {A} _{12}-\mathbf {S} _{2})\mathbf {B} _{22}} M 7 = A 22 ( S 4 − B 21 ) {\displaystyle \mathbf {M} _{7}=\mathbf {A} _{22}(\mathbf {S} _{4}-\mathbf {B} _{21})} T 1 = M 1 + M 2 {\displaystyle \mathbf {T} _{1}=\mathbf {M} _{1}+\mathbf {M} _{2}} T 2 = T 1 + M 4 {\displaystyle \mathbf {T} _{2}=\mathbf {T} _{1}+\mathbf {M} _{4}}
이 때 행렬 곱셈의 결과는 다음과 같이 주어진다.
C 11 = M 2 + M 3 {\displaystyle \mathbf {C} _{11}=\mathbf {M} _{2}+\mathbf {M} _{3}} C 12 = T 1 + M 5 + M 6 {\displaystyle \mathbf {C} _{12}=\mathbf {T} _{1}+\mathbf {M} _{5}+\mathbf {M} _{6}} C 21 = T 2 − M 7 {\displaystyle \mathbf {C} _{21}=\mathbf {T} _{2}-\mathbf {M} _{7}} C 22 = T 2 + M 5 {\displaystyle \mathbf {C} _{22}=\mathbf {T} _{2}+\mathbf {M} _{5}}
빅터 판(Victor Pan)은 슈트라센 알고리즘에서 행렬을 더 잘게 나눠서 O(n2.795)의 시간 안에 행렬을 곱하는 방법을 개발했다. 그는 68×68 행렬은 132,464번의 곱셈으로, 70×70 행렬은 143,640번의 곱셈으로, 72×72 행렬은 155,424번의 곱셈으로 계산이 가능함을 보였다.
돈 코퍼스미스(Don Coppersmith)와 슈무엘 위노그라드는 1987년에 또 다른 알고리즘인 코퍼스미스-위노그라드 알고리즘(Coppersmith–Winograd algorithm)을 개발했다. 이 알고리즘 역시 슈트라센 알고리즘처럼 재귀적 발상에서 나온 것으로, 시간 복잡도가 O(n2.376)이고 2010년에 Stother가 O(n2.3737)로 개선할 때까지 가장 빠른 알고리즘이었다. 이듬해 월리엄스가 O(n2.3727)로 개선한 알고리즘이 현존하는 가장 빠른 알고리즘이다. 2005년에는 이 알고리즘을 군론적 구성을 사용해 유도한 논문이 발표되었다.
참고 자료 및 각주 [ 편집 ]
↑ Paolo D’Alberto, Alexandru Nicolau, “Adaptive Strassen and ATLAS’s DGEMM: A Fast Square-Matrix Multiply for Modern High-Performance Systems,” hpcasia, pp. 45-52, Eighth International Conference on High-Performance Computing in Asia-Pacific Region (HPCASIA’05), 2005.
Strassen, Volker, Gaussian Elimination is not Optimal , Numer. Math. 13, p. 354-356, 1969
, Numer. Math. 13, p. 354-356, 1969 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms , Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 28: Section 28.2: Strassen’s algorithm for matrix multiplication, pp.735–741.
, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 28: Section 28.2: Strassen’s algorithm for matrix multiplication, pp.735–741. Henry Cohn, Robert Kleinberg, Balazs Szegedy, and Chris Umans. Group-theoretic Algorithms for Matrix Multiplication. Proceedings of the 46th Annual Symposium on Foundations of Computer Science , 23-25 October 2005, Pittsburgh, PA, IEEE Computer Society, pp. 379–388.
, 23-25 October 2005, Pittsburgh, PA, IEEE Computer Society, pp. 379–388. Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 9:251–280, 1990.
Strassen Algorithm
void strassen ( double * a , double * b , double * c , int ma , int mb , int mc , int p , int q , int r ) { if (( long long ) p * q * r <= 36000 ) { for ( int i = 0 ; i < p ; ++ i ) { for ( int k = 0 ; k < q ; ++ k ) { double t = a [ i * ma + k ]; if ( t == 0.0 ) continue ; for ( int j = 0 ; j < r ; ++ j ) { c [ i * mc + j ] += t * b [ k * mb + j ]; } } } return ; } int pp = p / 2 , qq = q / 2 , rr = r / 2 ; double * m1 = ( double * ) calloc ( pp * rr , sizeof ( double )); double * m2 = ( double * ) calloc ( pp * rr , sizeof ( double )); double * m3 = ( double * ) calloc ( pp * rr , sizeof ( double )); double * m4 = ( double * ) calloc ( pp * rr , sizeof ( double )); double * m5 = ( double * ) calloc ( pp * rr , sizeof ( double )); double * at1 = ( double * ) malloc ( sizeof ( double ) * pp * qq ); double * at2 = ( double * ) malloc ( sizeof ( double ) * pp * qq ); double * at3 = ( double * ) malloc ( sizeof ( double ) * pp * qq ); double * bt1 = ( double * ) malloc ( sizeof ( double ) * qq * rr ); double * bt2 = ( double * ) malloc ( sizeof ( double ) * qq * rr ); double * bt3 = ( double * ) malloc ( sizeof ( double ) * qq * rr ); int i , j ; double t1 , t2 , t3 , t4 , t5 ; for ( i = 0 ; i < pp ; ++ i ) for ( j = 0 ; j < qq ; ++ j ) { t1 = a [ i * ma + j ]; t2 = a [( i + pp ) * ma + j + qq ]; at1 [ i * qq + j ] = t1 + a [ i * ma + j + qq ]; at2 [ i * qq + j ] = t1 + t2 ; at3 [ i * qq + j ] = t2 + a [( i + pp ) * ma + j ]; } for ( i = 0 ; i < qq ; ++ i ) for ( j = 0 ; j < rr ; ++ j ) { t1 = b [ i * mb + j ]; t2 = b [( i + qq ) * mb + j + rr ]; bt1 [ i * rr + j ] = t1 ; bt2 [ i * rr + j ] = t1 + t2 ; bt3 [ i * rr + j ] = t2 ; } strassen ( at1 , bt3 , m5 , qq , rr , rr , pp , qq , rr ); strassen ( at2 , bt2 , m1 , qq , rr , rr , pp , qq , rr ); strassen ( at3 , bt1 , m2 , qq , rr , rr , pp , qq , rr ); for ( i = 0 ; i < qq ; ++ i ) for ( j = 0 ; j < rr ; ++ j ) { bt1 [ i * rr + j ] += b [ i * mb + j + rr ]; bt3 [ i * rr + j ] += b [( i + qq ) * mb + j ]; } for ( i = 0 ; i < pp ; ++ i ) for ( j = 0 ; j < qq ; ++ j ) { t1 = at2 [ i * qq + j ]; at1 [ i * qq + j ] -= t1 ; at3 [ i * qq + j ] -= t1 ; } strassen ( at1 , bt3 , c , qq , rr , mc , pp , qq , rr ); strassen ( at3 , bt1 , c + pp * mc + rr , qq , rr , mc , pp , qq , rr ); for ( i = 0 ; i < qq ; ++ i ) for ( j = 0 ; j < rr ; ++ j ) { t1 = bt2 [ i * rr + j ]; bt1 [ i * rr + j ] -= t1 ; bt3 [ i * rr + j ] -= t1 ; } strassen ( a , bt1 , m3 , ma , rr , rr , pp , qq , rr ); strassen ( a + pp * ma + qq , bt3 , m4 , ma , rr , rr , pp , qq , rr ); for ( i = 0 ; i < pp ; ++ i ) for ( j = 0 ; j < rr ; ++ j ) { t1 = m1 [ i * rr + j ]; t2 = m2 [ i * rr + j ]; t3 = m3 [ i * rr + j ]; t4 = m4 [ i * rr + j ]; t5 = m5 [ i * rr + j ]; c [ i * mc + j ] += t1 + t4 - t5 ; c [ i * mc + j + rr ] += t3 + t5 ; c [( i + pp ) * mc + j ] += t2 + t4 ; c [( i + pp ) * mc + j + rr ] += t1 - t2 + t3 ; } free ( m1 ); free ( m2 ); free ( m3 ); free ( m4 ); free ( m5 ); free ( at1 ); free ( at2 ); free ( at3 ); free ( bt1 ); free ( bt2 ); free ( bt3 ); } void matmul_strassen ( double * a , double * b , double * c , int p , int q , int r ) { int pp = p , qq = q , rr = r ; int mod = 1 ; while (( long long ) pp * qq * rr > 36000 ) { if ( pp & 1 ) pp ++ ; pp >>= 1 ; if ( qq & 1 ) qq ++ ; qq >>= 1 ; if ( rr & 1 ) rr ++ ; rr >>= 1 ; mod <<= 1 ; } pp *= mod ; qq *= mod ; rr *= mod ; double * a_re = ( double * ) calloc ( pp * qq , sizeof ( double )); double * b_re = ( double * ) calloc ( qq * rr , sizeof ( double )); double * c_re = ( double * ) calloc ( pp * rr , sizeof ( double )); for ( int i = 0 ; i < p ; ++ i ) { for ( int j = 0 ; j < q ; ++ j ) { a_re [ i * qq + j ] = a [ i * q + j ]; } } for ( int i = 0 ; i < q ; ++ i ) { for ( int j = 0 ; j < r ; ++ j ) { b_re [ i * rr + j ] = b [ i * r + j ]; } } strassen ( a_re , b_re , c_re , qq , rr , rr , pp , qq , rr ); for ( int i = 0 ; i < p ; ++ i ) { for ( int j = 0 ; j < r ; ++ j ) { c [ i * r + j ] += c_re [ i * rr + j ]; } } free ( a_re ); free ( b_re ); free ( c_re ); }
[분할 정복] Strassen algorithm
분할 정복 알고리즘(Divide and conquer algorithm) 중에 하나인 Strassen을 알아보자.
중고등학생 때 행렬의 곱셈에 대해 배웠을 것이다.
행렬 간에 곱셈을 하기 전에 곱셈이 가능한 행과 열로 행렬들이 갖춰졌는지 확인해야 하지만
우리는 정사각 행렬(Square matrix)만 다루기로 하자.
아래와 같이 각 크기가 n인 정사각 행렬 A, B가 있다고 하자.
$$ A_{n,n} = \begin{bmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} \end{bmatrix} $$
$$ B_{n,n} = \begin{bmatrix} b_{1,1} & b_{1,2} & \cdots & b_{1,n} \\ b_{2,1} & b_{2,2} & \cdots & b_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ b_{n,1} & b_{n,2} & \cdots & b_{n,n} \end{bmatrix} $$
행렬곱 C = AB는 아래와 같이 크기 n인 정사각 행렬로 정의된다.
$$ C_{n,n} = \begin{bmatrix} c_{1,1} & c_{1,2} & \cdots & c_{1,n} \\ c_{2,1} & c_{2,2} & \cdots & c_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ c_{n,1} & c_{n,2} & \cdots & c_{n,n} \end{bmatrix} $$
이때 행렬 C의 성분은 아래와 같이 정의된다.
$$ c_{i,j} = a_{i,1}b_{1,j} + a_{i,2}b_{2,j} + \cdots + a_{i,n}b_{n,j} = \sum_{k=1}^{n} a_{i,k}b_{k,j} $$
이를 다시 정리하면 행렬 C는 아래와 같은 모습이 된다.
$$ C_{n,n} = \begin{bmatrix} a_{1,1}b_{1,1}+\cdots+a_{1,n}b_{n,1} & a_{1,1}b_{1,2}+\cdots+a_{1,n}b_{n,2} & \cdots & a_{1,1}b_{1,n}+\cdots+a_{1,n}b_{n,n} \\ a_{2,1}b_{1,1}+\cdots+a_{2,n}b_{n,1} & a_{2,1}b_{1,2}+\cdots+a_{2,n}b_{n,2} & \cdots & a_{2,1}b_{1,n}+\cdots+a_{2,n}b_{n,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n,1}b_{1,1}+\cdots+a_{n,n}b_{n,1} & a_{n,1}b_{1,2}+\cdots+a_{n,n}b_{n,2} & \cdots & a_{n,1}b_{1,n}+\cdots+a_{n,n}b_{n,n} \end{bmatrix} $$
출처 : ko.wikipedia.org/wiki/%ED%96%89%EB%A0%AC_%EA%B3%B1%EC%85%88
코드로 표현하면 아래와 같다.
int** MultiplyMatrix(int** A, int** B, std::size_t n) { int** C = new int*[n]; int sum = 0; for (std::size_t i = 0; i < n; ++i) { C[i] = new int[n]; for (std::size_t j = 0; j < n; ++j) { sum = 0; for (std::size_t k = 0; k < n; ++k) { sum += (A[i][k] * B[k][j]); } C[i][j] = sum; } } return C; } 이를 시간 복잡도와 공간 복잡도로 표현하면 아래와 같다. $$time\,complexity\,:\,\Theta(n^{3})\quad space\,complexity\,:\,O(1)$$ 3중 반복문이 행렬의 크기 n만큼 돌기 때문에 $\Theta(n^{3})$의 시간 복잡도가 나오고 새로 생성할 행렬 C의 공간을 제외하면 sum 변수 정도를 위한 공간을 사용하기 때문에 $\Theta(1)$ 공간 복잡도가 나온다. 이렇게 행렬의 곱을 구하는 방법을 [방법 1]이라고 하자. 크기가 n인 정사각 행렬 곱셈의 시간 복잡도가 [방법 1]보다 더 나은 것이 없다고 생각할 수 있지만 Strassen 알고리즘을 사용하면 더 나은 시간 복잡도를 얻을 수 있다. 원리를 간단하게 설명하자면 행렬들을 쪼개서 곱하고 더하는 과정을 재귀적으로 반복하는데 행렬의 덧셈이 곱셈보다 더 빠른 점을 이용하기 위해 쪼갠 행렬들의 곱셈 횟수를 줄이고 덧셈 횟수를 늘린다. (곱셈은 앞서 본 것처럼 $\Theta(n^{3})$이지만 덧셈은 $\Theta(n^{2})$으로 더 나은 시간 복잡도를 가진다.) Strassen 알고리즘을 본격적으로 설명하기 앞서 재귀적으로 행렬을 쪼개어 곱하고 더하는 방법을 먼저 살펴보자. 행렬을 재귀적으로 쪼개는 작업이 n을 2로 계속 나누기 때문에 사전에 행렬들의 크기를 2의 거듭제곱으로 맞춰 놓는게 좋다. 그 다음 행렬 A와 B, C를 아래와 같이 각각 4분할로 쪼갠다. $$ A = \begin{bmatrix} A_{1,1} & A_{1,2} \\ A_{2,1} & A_{2,2} \end{bmatrix},\, B = \begin{bmatrix} B_{1,1} & B_{1,2} \\ B_{2,1} & B_{2,2} \end{bmatrix},\, C = \begin{bmatrix} C_{1,1} & C_{1,2} \\ C_{2,1} & C_{2,2} \end{bmatrix} $$ 쪼개진 행렬들로 다음 식들이 성립될 수 있다. $$ [식 1] \quad C_{1,1} = A_{1,1}B_{1,1} + A_{1,2}B_{2,1} $$ $$ [식 2] \quad C_{1,2} = A_{1,1}B_{1,2} + A_{1,2}B_{2,2} $$ $$ [식 3] \quad C_{2,1} = A_{2,1}B_{1,1} + A_{2,2}B_{2,1} $$ $$ [식 4] \quad C_{2,2} = A_{2,1}B_{1,2} + A_{2,2}B_{2,2} $$ 위 식들에 있는 행렬끼리의 곱에서 다시 위 과정을 재귀적으로 반복한다. 행렬의 크기가 더이상 쪼개지지 않는 1까지 반복하고 1개 요소만 남았으면 그냥 곱해주면 된다. 이렇게 행렬의 곱을 구하는 방법을 [방법 2]라고 하자. 그리고 아래와 같이 [방법 2]의 실행 시간을 정의할 수 있다. $$ T(n) = \begin{cases} \Theta(1), & \text{if }n = 1 \\ 8T(n/2) + \Theta(n^{2}), & \text{if }n > 1 \end{cases} $$
[식 1~4]에서 쪼개진 행렬들의 곱이 8번 일어나고 그 행렬의 크기는 n/2가 된다.그리고 행렬들의 덧셈이 4번 일어나는데 $4(n/2)^{2}$가 곧 $\Theta(n^{2})$가 된다.
$\Theta(n^{2}) = cn^{2} \quad \text{where}\, c > 0\,$로 정의하고 T(n)에 대해서 구체적으로 알아보자.
T(n)을 트리로 나타내면 아래와 같다.
[트리 1] [트리 1]은 부모 노드가 각각 8개씩 자식 노드를 갖고 있는 트리이다.(…으로 표시된 노드는 다 표시하지 못한 나머지 자식 노드들임을 알아두자.
그리고 첫 번째 자식 노드만 비교적 구체적으로 표현했고 나머지 노드들도 그런 식으로 자식 노드들이 있어야 한다.)
부모 노드에서는 자식 노드들에서 행렬 곱셈한 결과로 나온 행렬들을 더하는 작업의 실행 시간을 나타낸다.
트리의 높이는 $\log_{2} n$이고 리프 노드의 개수는 $8^{\log_{2}n} = n^{3}$이다.
(트리의 높이는 n을 1이 될 때까지 2로 몇 번 나눌 수 있는가이고
리프 노드 개수는 트리 깊이가 1씩 증가할 때마다 8배씩 증가하므로 $8^{\log_{2}n} = n^{3}$이 된다.)
트리의 총 실행 시간을 (리프 노드들을 제외한 모든 레벨의 총 실행 시간) + (리프 노드들의 총 실행 시간)으로 구하면 아래와 같다.
$$ \begin{align} T(n) &= (cn^{2} + 8c(n/2)^{2} + 8^{2}c(n/4)^{2} + \cdots + (8/4)^{(\log_{2} n)-1}cn^{2}) + (\Theta(n^{3})) \\ &= \sum_{k=0}^{(\log_{2} n)-1} 2^{k}cn^{2} + \Theta(n^{3}) = {cn^{2}(2^{\log_{2}n} – 1) \over (2 – 1)} + \Theta(n^{3}) \\ &= cn^{2}(n – 1) + \Theta(n^{3}) = \Theta(n^{3}) \end{align} $$
결국 [방법 2]는 [방법 1]과 같은 시간 복잡도를 갖는다.
이제 Strassen 알고리즘을 알아보자.
아래와 같이 7개의 행렬을 정의해 보자.
$$ \begin{align} &M_{1} = (A_{1,1} + A_{2,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_{2,1} – B_{1,1}) \\ &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} $$
그리고 위의 행렬들로 아래의 식들이 성립된다.
$$ \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} $$
위 식들을 직접 전개해 보면 [식 1~4]가 그대로 나온다.
출처 : 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
앞서 간단하게 설명했던 것과 같이 행렬의 곱셈을 1번 줄이는 대신 행렬의 덧셈을 여러번 더 수행한 셈이다.
행렬의 덧셈이 비록 여러번 더 수행되었지만 이는 $n^{2}$의 상수배에 달하는 시간이고 이는 결국 $\Theta(n^{2})$에 종결된다.
다시 실행 시간 T(n)을 정의해 보면 아래와 같다.
(굳이 다시 트리로 펼치지 않고 식으로 정의하겠다.)
$$ \begin{align} T(n) &= 7T(n/2) + \Theta(n^{2}) \\ &= (cn^{2} + 7c(n/2)^{2} + 7^{2}c(n/4)^{2} + \cdots + ({7 \over 4})^{(\log_{2} n)-1}cn^{2}) + \Theta(n^{\log_{2} 7}) \\ &= \sum_{k=0}^{(\log_{2} n) – 1} ({7 \over 4})^{k}cn^{2} + \Theta(n^{\log_{2} 7}) \\ &= {{7 \over 4}^{\log_{2} n} – 1 \over {7 \over 4} – 1}cn^{2} + \Theta(n^{\log_{2} 7}) \\ &= {4 \over 3}c(n^{\log_{2} 7} – n^{2}) + \Theta(n^{\log_{2} 7}) \\ &= \Theta(n^{\log_{2} 7}) \quad \because \, 2.80 < \log_{2} 7 < 2.81 \end{align} $$ 트리의 높이는 $\log_{2} n$으로 [방법 2]와 같지만 부모 노드의 자식 노드 개수가 8개에서 7개로 감소했다. 그래서 리프 노드들의 총 실행 시간은 $\Theta(n^{\log_{2} 7})$이 된다. (트리의 각 레벨에 있는 노드들의 개수는 $7^{k}$(사실 k는 깊이(레벨-1)이다.)이고 마지막 레벨인 $\log_{2} n$을 $k$에 대입하면 $7^{\log_{2} n}$이 되며 이는 곧 $n^{\log_{2} 7}$이 된다.) 따라서 Strassen 알고리즘은 [방법 1]과 [방법 2]보다 더 나은 시간 복잡도를 보여주고 있다. 공간 복잡도는 어떨까? 먼저 처음 $M_{1,2, \cdots, 7}$을 위한 공간이 필요하므로 여러 개의 $(n/2)^{2}$ 크기의 공간이 필요하다. 그 다음은 여러 개의 $(n/4)^{2}$ 크기가 필요하고 이런 식으로 $n^{2}$의 상수배 공간들이 필요하게 된다. (멀티 스레드가 아니면 어떤 노드와 그 노드의 사촌 노드를 위한 공간을 동시에 필요로 하지 않는다. 즉, 실행 시간과 달리 공간은 트리의 깊이에 따라 7배씩 증가하지 않는다.) 따라서 $\Theta(n^{2})$으로 볼 수 있다. 다음으로 실제 실행 시간에 대해서 생각해보자. Strassen 알고리즘은 여러 행렬 덧셈을 수행하므로 매우 큰 $n$이 아니면 [방법 1]보다 오래 걸린다. 필자도 Strassen 알고리즘이 더 빠른 $n$을 찾고자 여러 시도를 해봤는데 실행 시간이 감당이 되지 않고 메모리도 부족하여 일반 가정용 컴퓨터로 찾기에는 무리인 것으로 판단했다. (Strassen 알고리즘을 멀티 스레드로 돌려도 답이 없다. 측정 가능한 $n$들에 대해 걸리는 시간을 그래프로 그리고 Strassen 알고리즘이 더 빨라지는 $n$을 추론하는 방법이 있겠다.) 마지막으로 Strassen 알고리즘을 코드로 표현하면 아래와 같다. class Matrix { typedef int (*Calculate)(int, int); static int Add(int value1, int value2) { return value1 + value2; } static int Sub(int value1, int value2) { return value1 - value2; } static int Set(int value1, int value2) { return value2; } Matrix(const Matrix& other, std::size_t row1, std::size_t col1, std::size_t row2, std::size_t col2, std::size_t size, Calculate cal) { _n = _size = size; _useStrassen = other._useStrassen; // it must be true _name = other._name; _values = new Value * [_size]; for (std::size_t i = 0; i < _size; ++i) { _values[i] = new Value[_size]; for (std::size_t j = 0; j < _size; ++j) { _values[i][j] = cal(other[row1 + i][col1 + j], other[row2 + i][col2 + j]); } } } Matrix(const Matrix& other, std::size_t row, std::size_t col, std::size_t size) { _n = _size = size; _useStrassen = other._useStrassen; _name = other._name; _values = new Value * [_size]; for (std::size_t i = 0; i < _size; ++i) { _values[i] = new Value[_size]; memcpy(_values[i], other[row + i] + col, _size); } } void Calc(const Matrix& other, std::size_t row, std::size_t rowCount, std::size_t col, std::size_t colCount, Calculate cal) { for (std::size_t i = 0; i < rowCount; ++i) { for (std::size_t j = 0; j < colCount; ++j) { _values[row + i][col + j] = cal(_values[row + i][col + j], other[i][j]); } } } void Strassen(const Matrix& other, std::size_t thisRow, std::size_t thisCol, std::size_t otherRow, std::size_t otherCol) { // reference : 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 if (1 < _size) { std::size_t half = _size / 2; Matrix M1(*this, thisRow, thisCol, thisRow + half, thisCol + half, half, Add); // M1 = A11 + A22 M1.Strassen(Matrix(other, otherRow, otherCol, otherRow + half, otherCol + half, half, Add), 0, 0, 0, 0); // M1 *= (B11 + B22) Matrix M2(*this, thisRow + half, thisCol, thisRow + half, thisCol + half, half, Add); // M2 = A21 + A22 M2.Strassen(other, 0, 0, otherRow, otherCol); // M2 *= B11 Matrix M3(*this, thisRow, thisCol, half); // M3 = A11 M3.Strassen(Matrix(other, otherRow, otherCol + half, otherRow + half, otherCol + half, half, Sub), 0, 0, 0, 0); // M3 *= (B12 - B22) Matrix M4(*this, thisRow + half, thisCol + half, half); // M4 = A22 M4.Strassen(Matrix(other, otherRow + half, otherCol, otherRow, otherCol, half, Sub), 0, 0, 0, 0); // M4 *= (B21 - B11) Matrix M5(*this, thisRow, thisCol, thisRow, thisCol + half, half, Add); // M5 = A11 + A12 M5.Strassen(other, 0, 0, otherRow + half, otherCol + half); // M5 *= B22 Matrix M6(*this, thisRow + half, thisCol, thisRow, thisCol, half, Sub); // M6 = A21 - A11 M6.Strassen(Matrix(other, otherRow, otherCol, otherRow, otherCol + half, half, Add), 0, 0, 0, 0); // M6 *= (B11 + B12) Matrix M7(*this, thisRow, thisCol + half, thisRow + half, thisCol + half, half, Sub); // M7 = A12 - A22 M7.Strassen(Matrix(other, otherRow + half, otherCol, otherRow + half, otherCol + half, half, Add), 0, 0, 0, 0); // M7 *= (B21 + B22) // for C11 //Calc(M1, 0, half, 0, half, Set); // C11 = M1 for (std::size_t i = 0; i < half; ++i) { memcpy(_values[i], M1[i], half); } Calc(M4, 0, half, 0, half, Add); // C11 += M4 Calc(M5, 0, half, 0, half, Sub); // C11 -= M5 Calc(M7, 0, half, 0, half, Add); // C11 += M7 // for C12 //Calc(M3, 0, half, half, half, Set); // C12 = M3 for (std::size_t i = 0; i < half; ++i) { memcpy(_values[i] + half, M3[i], half); } Calc(M5, 0, half, half, half, Add); // C12 += M5 // for C21 //Calc(M2, half, half, 0, half, Set); // C21 = M2 for (std::size_t i = 0; i < half; ++i) { memcpy(_values[half + i], M2[i], half); } Calc(M4, half, half, 0, half, Add); // C21 += M4 // for C22 //Calc(M1, half, half, half, half, Set); // C22 = M1 for (std::size_t i = 0; i < half; ++i) { memcpy(_values[half + i] + half, M1[i], half); } Calc(M2, half, half, half, half, Sub); // C22 -= M2 Calc(M3, half, half, half, half, Add); // C22 += M3 Calc(M6, half, half, half, half, Add); // C22 += m6 } else { _values[thisRow][thisCol] *= other[otherRow][otherCol]; Progress::Proceed(_name, 1); } } void Strassen(const Matrix&& other, std::size_t row1, std::size_t col1, std::size_t row2, std::size_t col2) { Strassen(other, row1, col1, row2, col2); } }; Strassen 알고리즘의 주요 코드 일부를 가져왔다. 최대한 새로운 행렬을 생성하는 것을 막고자 인덱스로 행렬 성분들을 참조하도록 구현했다. (그리고 recurrence를 iteration으로 바꾸면 더욱 효율적일 것이다.) 여기까지 Strassen 알고리즘에 대해 알아보았다.
알고리즘: 슈트라센(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번 있으므로)
여기서 도사정리를 이용하면
위와 같음을 알 수 있다.
반응형
슈트라센 알고리즘 증명
슈트라센 알고리즘 증명
슈트라센 알고리즘 증명
Proof of strassen algorithm
목차 알고리즘
설명
증명
알고리즘
$k \in \mathbb{N}$ 에 대해 $n=2^{k}$ 이라고 하자. $A, B \in \mathbb{R}^{n \times n}$ 에 대해 조던 블록 행렬 표현을 사용해 다음과 같은 8개의 ${{n} \over {2}} \times {{n} \over {2}}$ 행렬 $A_{i}$, $B_{i}$ 들을 생각해보자. $$ AB= \begin{bmatrix} A_{1} & A_{2} \\ A_{3} & A_{4} \end{bmatrix} \begin{bmatrix} B_{1} & B_{2} \\ B_{3} & B_{4} \end{bmatrix} = \begin{bmatrix} C_{1} & C_{2} \\ C_{3} & C_{4} \end{bmatrix} = C $$ $C = AB$ 를 구하기 위해 다음을 계산한다. $$ P_{1} = A_{1} ( B_{2} – B_{4} ) \\ P_{2} = ( A_{1} + A_{2} ) B_{4} \\ P_{3} = ( A_{3} + A_{4} ) B_{1} \\ P_{4} = A_{4} ( B_{3} – B_{1} ) \\ P_{5} = (A_{1} + A_{4}) ( B_{1} + B_{4} ) \\ P_{6} = (A_{2} – A_{4}) ( B_{3} + B_{4} ) \\ P_{7} = (A_{3} – A_{1}) ( B_{1} + B_{2} ) $$
$$ C_{1} = -P_{2} + P_{4}+ P_{5} + P_{6} \\ C_{2} = P_{1} + P_{2} \\ C_{3} = P_{3} + P_{4} \\ C_{4} = P_{1} – P_{3} + P_{5} + P_{7} $$ $A_{i} B_{j}$ 를 계산할 때도 같은 방법을 반복하면 그 시간복잡도는 $\Theta ( n^{2.807} )$ 이다.
물론 $n
e 2^{k}$ 라고 해서 쓸 수 없는 것은 아니고, 사이즈를 조정해서 그대로 적용시켜도 된다.
설명
상식적이고 곧바로 떠올릴 수 있는 행렬의 곱셈은 $$ C_{1} = A_{1}B_{1} + A_{2} B_{3} \\ C_{2} = A_{1}B_{2} + A_{2} B_{4} \\ C_{3} = A_{3}B_{1} + A_{4} B_{3} \\ C_{4} = A_{3}B_{2} + A_{4} B_{4} $$ 이 계산을 계속 반복하면 되는데, 여기에 걸리는 시간이 $\Theta ( n^3 )$ 라는 것은 의심의 여지가 없었다.
슈트라센이 태어나기 전까진 말이다.
이 알고리즘은 아주 아주 획기적인데, 본디 한 개의 $C_{i}$ 을 계산하는데는 반드시 두 번의 행렬 곱셈이 필요하기 때문이다. 합쳐서 한번 계산할 때마다 8번을 계산해야하는데, 슈트라센은 이것을 7번으로 줄였다. 저 방법 외에 달리 방법이 있을까 고민한 것부터가 비범한 센스고, 정말 찾아낸 것은 불가사의하다고까지 말할 수 있을 정도다. 이 알고리즘의 개발로 인해서 행렬 계산에 쓰였을 자원들을 조금이나마, 아니 엄청나게 많이 아낄 수 있다.
증명
Part 1. 계산가능성
그냥 직접 계산해보는 수밖에 없다.
Part 1-1. $C_{1} = A_{1}B_{1} + A_{2} B_{3}$
$$ \begin{align*} C_{1} =& -P_{2} + P_{4} + P_{5} + P_{6} \\ =& ( {\color{red}- A_{1} B_{4}} – A_{2} B_{4} ) + P_{4} + ( A_{1}B_{1} + {\color{red} A_{1}B_{4} } + A_{4} B_{1} + A_{4}B_{4} ) + P_{6} \\ =& – A_{2} B_{4} + (A_{4} B_{3} {\color{red}- A_{4} B_{1} }) + A_{1}B_{1} + {\color{red} A_{4} B_{1} } + A_{4}B_{4} + P_{6} \\ =& {\color{red} – A_{2} B_{4} } + \color{blue}{A_{4} B_{3} } + A_{1}B_{1} + \color{green}{A_{4}B_{4}} + ( A_{2} B_{3} + {\color{red} A_{2} A_{4} } \color{blue}{ – A_{4} B_{3} }- \color{green}{A_{4} B_{4}}) \\ =& A_{1}B_{1} + A_{2} B_{3} \end{align*} $$
Part 1-2. $C_{2} = A_{1}B_{2} + A_{2} B_{4}$
$$ \begin{align*} C_{2} =& P_{1} + P_{2} \\ =& (A_{1}B_{2} {\color{red}- A_{1} B_{4}}) + ( {\color{red}A_{1} B_{4}} + A_{2} B_{4}) \\ =& A_{1}B_{2} + A_{2} B_{4} \end{align*} $$
Part 1-3. $C_{3} = A_{3}B_{1} + A_{4} B_{3}$
$$ \begin{align*} C_{3} =& P_{3} + P_{4} \\ =& (A_{3}B_{1} + {\color{red} A_{4}B_{1}}) + (A_{4}B_{3} {\color{red}- A_{4}B_{1}}) \\ =& A_{3}B_{1} + A_{4} B_{3} \end{align*} $$
Part 1-4. $C_{4} = A_{3}B_{2} + A_{4} B_{4}$
$$ \begin{align*} C_{4} =& P_{1} – P_{3} + P_{5} + P_{7} \\ =& (A_{1}B_{2} \color{red}{ – A_{1} B_{4}} ) – P_{3} + ( A_{1}B_{1} + \color{red}{A_{1}B_{4} }+ A_{4}B_{1} + A_{4}B_{4}) + P_{7} \\ =& A_{1}B_{2} + (- A_{3}B_{1} – {\color{red}A_{4}B_{1}}) + A_{1}B_{1} + {\color{red}A_{4}B_{1}} + A_{4}B_{4} + P_{7} \\ =& {\color{red} A_{1}B_{2}} – \color{blue}{A_{3}B_{1}} + \color{green}{A_{1}B_{1}}+ A_{4}B_{4} + ( \color{blue}{A_{3}B_{1}} + A_{3}B_{2} – \color{green}{A_{1}B_{1}} {\color{red}- A_{1}B_{2}}) \\ =& A_{3}B_{2} + A_{4} B_{4} \end{align*} $$
Part 2. 시간복잡도
본질적으로 원래의 계산법이 $\Theta ( n^3 )$ 이라는 것을 증명한 방법과 같다. 한번 계산하는데 걸리는 시간이 $T(n)$ 이고 반복 외의 수행시간을 $c$ 라고 하면 $\displaystyle T(n) = 7 T \left( {{n} \over {2}} \right) + c$ 이므로
$$ \begin{align*} T(n) =& 7 T \left( {{n} \over {2}} \right) + c \\ =& 7 \left[ 7 T \left( {{n} \over {4}} \right) + c \right] + c \\ =& 7 \left[ 49 T \left( {{n} \over {8}} \right) + 7 c + c \right] + c \\ =& 7^3 T \left( {{n} \over {8}} \right) + (1+7+7^2)c \\ =& 7^3 T \left( {{n} \over {8}} \right) + {{7^3 – 1} \over {7 – 1}}c \\ & \vdots & \\ \approx& 7^{\log_{2} n} ( T(1) + c ) \\ =& n^{\log_{2} 7} ( T(1) + c ) \\ =& n^{2.807} ( T(1) + c ) \\ =& \Theta ( n^2.807 ) \end{align*} $$
■
[알고리즘]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
첨부파일에 있는 문서가 공부하시는데 많은 도움이 되실겁니다.
Strassen Algorithm
행렬의 곱셈
크기가 n x n인 두 행렬 A와B의 곱을 C로 나타내고자 한다.
의 원소를
라 하고,
는 가로
는 세로를 나타낸다.
B와 C도 동일하게 표시한다.
행렬의 곱셈을 다음과 같이 표현할 수 있다.
C하나의 원소를 구하는데 드는 비용은,
곱셈
번과
덧셈
번이다.
따라서, C 전체를 구할 경우 C의 크기는 n x n 이므로
곱셈을
번
그리고 덧셈을
번하게 된다.
따라서, 두행렬을 구하는 복잡도는
이 된다.
알고리즘
A와 B를 체 F에 대한 정사각행렬이라고 하자. 두 행렬의 곱 C는 다음과 같다.
만약 A와 B가 2ⁿ × 2ⁿ 꼴의 크기가 아니라면 먼저 모자라는 행과 열을 0으로 채운다.
이 경우 행렬 곱셈이 끝난 뒤 행렬에서 필요한 부분만 다시 잘라 내야 한다.
이제 A, B, C를 같은 크기의 정사각행렬 네 개로 나눈다.
이 때,
따라서 다음이 성립한다.
이 과정에서는 필요한 연산의 수가 줄어 들지 않는다. 여전히 Ci, j 행렬을 계산하려면 여덟 번의 곱셈과 네 번의 덧셈이 필요하다.
이제 다음과 같은 행렬을 정의한다.
이 Mk 행렬들은 Ci,j 행렬을 표현하는 데 쓰이는데, 이 행렬들을 계산하는 데는 일곱 번의 곱셈(각 변수마다 한 번씩)과 10번의 덧셈이 필요하다. 이제 Ci,j 행렬은 다음과 같이 표현할 수 있다.
이 과정에서는 곱셈이 사용되지 않기 때문에, 전체 곱셈을 일곱 번의 곱셈과 18번의 덧셈(8+10)으로 처리할 수 있다. 큰 행렬에 대해서는 행렬의 곱셈이 덧셈보다 더 많은 시간을 필요로 하기 때문에 덧셈을 더 하는 대신 곱셈을 덜 하는 것이 전체적으로 더 효율적이다.
이 과정을 재귀적으로 반복할 경우 총
번의 연산이 필요하다.
실제로는 n이 작을 경우 정의에 따라 행렬 곱셈을 하는 경우가 빠를 수도 있기 때문에, 보통 작은 n에 대해서는 일반적인 방법으로 곱셈을 하도록 구현한다.슈트라센 알고리즘은 속도에 비해 수치 안정성이 떨어지는 것으로 알려져 있다.
두 행렬 A와 B를 곱한 결과를 C라 할 때, 실제 오차인
는
보다 작음이 알려져 있다. 이는 일반적인 행렬 곱셈보다 더 큰 오차이다.
스트라센의 경우 행렬의 곱셉을 하기 위해서는 정사각행렬에 대해서만 처리가 가능하다. 그렇지 않을 경우에는 행렬을 정사각 행렬로 변경하는 작업이 필요하다. 또한, 특정 단계에서는 행렬의 곱이 더 빠른 구간이 있으며 스트라센 행렬에서는 최적의 행렬 크기에서는 일반곱으로 행렬을 풀어나가는 방법이 있다. 스트라센 알고리즘에서 또 눈여겨 볼 부분은 연산으로 사용하는 M행렬을 구하는 부분에서도 행렬의 곱이 쓰인다는 점이다. 행렬의 곱은 스트라센으로 풀어나가는 알고리즘이기 때문에 M1을 예로 들면 M1 := (A + A) strassen (A + B) 이런식으로 풀어 쓸수 있다. 결국에는 재귀적인 호출을 통해 스트라센을 구해 나가는 방식을 이용하는 알고리즘인것 이다. 분할 정복알고리즘과 동일하며, M에서는 각 행렬을 작은 단위로 분할하며 최종 C행렬을 구하기 위해서는 분할된 원소를 재조립하는 과정으로 최종 행렬을 얻어낼 수 있다.
Python: 행렬 곱셈 알고리즘 소개
728×90
반응형
1. 소개
행렬 n x n 을 곱하려면, 보통 for 문 3개, O(n^3) 시간 복잡도를 갖지만,
// 일반 행렬 곱셈 int** multiply(int** A, int** B, int n) { int** C = initializeMatrix(n); setToZero(C, n); // 전부 0으로 초기화 for(int i=0; i
[알고리즘] 스트라센 (strassen)
1. 개요
행렬의 곱연산을 수행함에 있어 행렬이 커지면 커질수록 연산에 속도는 기하급수적으로 증가할 수밖에 없는 구조이다. 행렬의 곱은 각 원소를 곱한 후에 나온 결과를 더해 최종 행렬이 생성이 되며 행렬의 크기가 커질수록 곱하기 연산은 증가 할 수밖에 없다. cpu에 구조상 더하기 연산이 빠르기 때문에 스트라센 알고리즘에서는 곱하기 연산을 더하기 연산으로 치환하여 계산하도록 알고리즘을 보안했다.
2. 알고리즘 방법
아래 A, B 행렬과 두 행의 곱의 결과 C가 있다고 했을 때
일반적인 행렬의 곱은 다음과 같으며, 총 8번의 곱셉과 네번의 덧셈으로 연산된다.
스트라센에서 행렬의 곱셉을 더하기 연산으로 풀어 각 원소를 구할 수 있는 M이라는 연산 행렬로 표현한다.
이러한 M행렬은 일곱번의 곱셈과 10번의 덧셈으로 연산으로 나타낼 수 있으며 아래 와 같이 표현한다.
최종 C행렬은 M행렬의 더하기 연산으로 이루어져 있으며, 각 원소에 해당하는 방법이있다.
3. 결론
스트라센의 경우 행렬의 곱셉을 하기 위해서는 정사각행렬에 대해서만 처리가 가능하다. 그렇지 않을 경우에는 행렬을 정사각 행렬로 변경하는 작업이 필요하다. 또한, 특정 단계에서는 행렬의 곱이 더 빠른 구간이 있으며 스트라센 행렬에서는 최적의 행렬 크기에서는 일반곱으로 행렬을 풀어나가는 방법이 있다. 스트라센 알고리즘에서 또 눈여겨 볼 부분은 연산으로 사용하는 M행렬을 구하는 부분에서도 행렬의 곱이 쓰인다는 점이다. 행렬의 곱은 스트라센으로 풀어나가는 알고리즘이기 때문에 M1을 예로 들면 M1 := (A + A) strassen (A + B) 이런식으로 풀어 쓸수 있다. 결국에는 재귀적인 호출을 통해 스트라센을 구해 나가는 방식을 이용하는 알고리즘인것 이다. 분할 정복알고리즘과 동일하며, M에서는 각 행렬을 작은 단위로 분할하며 최종 C행렬을 구하기 위해서는 분할된 원소를 재조립하는 과정으로 최종 행렬을 얻어낼 수 있다.
4. 소스코드
public class Strassen { public static void main(String[] args ) { int n = 1024; int [][] x = initMetrix ( n ); int [][] y = initMetrix ( n ); int [][] nomalResult = Strassen. metrixMul ( n , x , y ); Strassen strassen = new Strassen(); int [][] strassenReslut = strassen .excuteStrassen( x , y ); boolean checkMetrix = true ; for ( int i = 0; i < n ; i ++) { for ( int j = 0; j < n ; j ++) { if ( nomalResult [ i ][ j ] != strassenReslut [ i ][ j ]) { checkMetrix = false ; } } } System. out .println( " 결과 : " + checkMetrix ); } public static int [][] initMetrix( int n ) { Random r = new Random(); int [][] resultMetrix = new int [ n ][ n ]; for ( int i = 0; i < n ; i ++) { for ( int j = 0; j < n ; j ++) { resultMetrix [ i ][ j ] = r .nextInt(30); } } return resultMetrix ; } public int [][] excuteStrassen( int [][] metrixX , int [][] metrixY ) { // 스트라센의 경우 n*n 행렬로 연산 int n = metrixX . length ; // 임계 차원 보다 작을 경우 기존 메트릭스 곱으로 풀이 if ( n <= 2) { return metrixMul ( n , metrixX , metrixY ); } // 4 등분 int rank = n / 2; // 배열 분해 int [][] a11 = subMetrix( rank , 0, 0, metrixX ); int [][] a12 = subMetrix( rank , 0, rank , metrixX ); int [][] a21 = subMetrix( rank , rank , 0, metrixX ); int [][] a22 = subMetrix( rank , rank , rank , metrixX ); int [][] b11 = subMetrix( rank , 0, 0, metrixY ); int [][] b12 = subMetrix( rank , 0, rank , metrixY ); int [][] b21 = subMetrix( rank , rank , 0, metrixY ); int [][] b22 = subMetrix( rank , rank , rank , metrixY ); int [][] m1 = excuteStrassen(metrixSum( a11 , a22 ), metrixSum( b11 , b22 )); // m1=(a11+a11)(b11+b22) int [][] m2 = excuteStrassen(metrixSum( a21 , a22 ), b11 ); // m2=(a21+a22)b11 int [][] m3 = excuteStrassen( a11 , metrixSub( b12 , b22 )); // m3=a11(b12-b22) int [][] m4 = excuteStrassen( a22 , metrixSub( b21 , b11 )); // m4=a22(b21-b11) int [][] m5 = excuteStrassen(metrixSum( a11 , a12 ), b22 ); // m5=(a11+a12)b22 int [][] m6 = excuteStrassen(metrixSub( a21 , a11 ), metrixSum( b11 , b12 )); // m6=(a21-a11)(b11+b12) int [][] m7 = excuteStrassen(metrixSub( a12 , a22 ), metrixSum( b21 , b22 )); // m7=(a12-a22)(a21+b22) // 결과 생성 int [][] c11 = metrixSum(metrixSub(metrixSum( m1 , m4 ), m5 ), m7 ); // c11 = m1 + m4 - m5 + m7 int [][] c12 = metrixSum( m3 , m5 ); // c12 = m3 + m5 int [][] c21 = metrixSum( m2 , m4 ); // c21 = m2 + m4 int [][] c22 = metrixSum(metrixSub(metrixSum( m1 , m3 ), m2 ), m6 ); // c22 = m1 + m3 - m2 + m6 // 결합 return combin( c11 , c12 , c21 , c22 ); } private int [][] combin( int [][] c11 , int [][] c12 , int [][] c21 , int [][] c22 ) { int n = c11 . length ; int [][] resultMetrix = new int [ n *2][ n *2]; for ( int i = 0; i < n ; i ++) { for ( int j = 0; j < n ; j ++) { resultMetrix [ i ][ j ] = c11 [ i ][ j ]; // 11 resultMetrix [ i ][ j + n ] = c12 [ i ][ j ]; // 12 resultMetrix [ i + n ][ j ] = c21 [ i ][ j ]; // 21 resultMetrix [ i + n ][ j + n ] = c22 [ i ][ j ]; // 22 } } return resultMetrix ; } private int [][] subMetrix( int n , int startX , int startY , int [][] metrix ) { int [][] subMetirx = new int [ n ][ n ]; for ( int i = 0, x = startX ; i < n ; i ++, x ++) { for ( int j = 0, y = startY ; j < n ; j ++, y ++) { subMetirx [ i ][ j ] = metrix [ x ][ y ]; } } return subMetirx ; } private int [][] metrixSum( int [][] metrixX , int [][] metrixY ) { int n = metrixX . length ; int [][] metrixResult = new int [ n ][ n ]; for ( int i = 0; i < n ; i ++) { for ( int j = 0; j < n ; j ++) { metrixResult [ i ][ j ] = metrixX [ i ][ j ] + metrixY [ i ][ j ]; } } return metrixResult ; } private int [][] metrixSub( int [][] metrixX , int [][] metrixY ) { int n = metrixX . length ; int [][] metrixResult = new int [ n ][ n ]; for ( int i = 0; i < n ; i ++) { for ( int j = 0; j < n ; j ++) { metrixResult [ i ][ j ] = metrixX [ i ][ j ] - metrixY [ i ][ j ]; } } return metrixResult ; } public static int [][] metrixMul( int n , int [][] metrixX , int [][] metrixY ) { int [][] result = new int [ n ][ n ]; for ( int i = 0; i < n ; i ++) { for ( int j = 0; j < n ; j ++) { for ( int k = 0; k < n ; k ++) { result [ i ][ j ] += metrixX [ i ][ k ] * metrixY [ k ][ j ]; } } } return result ; } } 5. 최종 결론 아마 제공된 코드를 수행하더라도 유익한 수행 시간을 얻어 낼 수 는 없을 것이다. 결국엔 자바에서나 C에서도 행렬을 구하는 과정에 산술연산이외에 추가로 필요한 작업들이 들어갔기 때문이다. 좀더 복잡한 과정을 통해 메모리 초기화 과정을 제거 할 수는 있으나 소스코드가 복잡해지기 때문에 이 쯤에서 멈추도록 하겠다.
키워드에 대한 정보 스트라 센 알고리즘
다음은 Bing에서 스트라 센 알고리즘 주제에 대한 검색 결과입니다. 필요한 경우 더 읽을 수 있습니다.
이 기사는 인터넷의 다양한 출처에서 편집되었습니다. 이 기사가 유용했기를 바랍니다. 이 기사가 유용하다고 생각되면 공유하십시오. 매우 감사합니다!
사람들이 주제에 대해 자주 검색하는 키워드 [알고리즘 실습] 제3강 분할정복: Part 2-1. 쉬트라쎈 행렬 곱셈
- 알고리즘
- 프로그래밍
- 코딩
- 컴퓨팅적사고
- 문제해결
- 컴퓨터과학
- 쉬트라쎈
- 행렬곱셈
- 분할정복
YouTube에서 스트라 센 알고리즘 주제의 다른 동영상 보기
주제에 대한 기사를 시청해 주셔서 감사합니다 [알고리즘 실습] 제3강 분할정복: Part 2-1. 쉬트라쎈 행렬 곱셈 | 스트라 센 알고리즘, 이 기사가 유용하다고 생각되면 공유하십시오, 매우 감사합니다.