행렬의 개요 행렬은 수를 원소로 지니는 다차원 배열이다. mn (“m by n”) 행렬은 m개의 행과 n개의 열을 갖는다. 행과 열의 개수가 같은 nxn 행렬을 정방행렬이라 한다. 두 행렬이 같은 수의 행과 열을 가지며 각 위치의 해당 원소의 값이 같으면 “두 행렬은 같다”고 정의한다.

행렬의 곱 행렬의 곱:  

행렬곱셈 – 단순 알고리즘 (1/3) 문제: n  n 크기의 행렬의 곱을 구하시오. 입력: 양수 n, n  n 크기의 행렬 A와 B 출력: 행렬 A와 B의 곱인 C 알고리즘: void matrixmul (int n, number[][] A, number[][] B, number[][] C){ index i, j, k; for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) { C[i][j] = 0; for (k = 1; k <= n; k++) C[i][j]=C[i][j] + A[i][k]*B[k][j]; }

행렬곱셈 – 단순 알고리즘 (2/3) 곱셈 연산의 시간복잡도 분석 - I 단위연산: 가장 안쪽의 루프에 있는 곱셈 연산 입력크기: 행과 열의 수, n 모든 경우 시간복잡도 분석: 총 곱셈의 횟수는 다음과 같다.

행렬곱셈 – 단순 알고리즘 (3/3) 곱셈 연산의 시간복잡도 분석 – II (P. 86 연습문제 25번) … 단위연산: 가장 안쪽의 루프에 있는 덧셈(뺄셈) 연산 입력크기: 행과 열의 수, n 모든 경우 시간복잡도 분석: 아래와 같이 약간만 알고리즘을 변경하면 총 덧셈의 횟수는 다음과 같다. … for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) { C[i][j] = A[i][1]*B[1][j]; for (k = 2; k <= n; k++) C[i][j]=C[i][j]+A[i][k]*B[k][j]; }

쉬트라쎈(Strassen) 방법 – 2x2 행렬 (1/2) 문제: 두 2  2 행렬 A와 B의 곱(product) C, 쉬트라쎈(Strassen)의 해: Why? 앉아서 꼼꼼히 따져보세요.

쉬트라쎈(Strassen) 방법 – 2x2 행렬 (2/2) 시간복잡도 분석: 단순 곱셈 방법: 8번의 곱셈과 4번의 덧셈이 필요함 쉬트라쎈 방법: 7번의 곱셈과 18번의 덧셈/뺄셈이 필요함  언뜻 봐서는 전혀 좋아지지 않았다!  그러나 행렬의 크기가 커지면 쉬트라쎈의 방법의 가치가 드러난다.

쉬트라쎈(Strassen) 방법 – nxn 행렬 (1/3) 문제: n이 2의 거듭제곱이고, 각 행렬을 4개의 부분행렬(submatrix)로 나눈다고 가정하자. 두 n  n 행렬 A와 B의 곱 C:

쉬트라쎈(Strassen) 방법 – nxn 행렬 (1/3)

쉬트라쎈(Strassen) 방법 – nxn 행렬 (2/3) 예 (수행과정의 일부 – M1 구하기)

쉬트라쎈(Strassen) 방법 – nxn 행렬 (3/3) 문제: n이 2의 거듭제곱일 때, n  n 크기의 두 행렬의 곱을 구하시오. 입력: 정수 n, n  n 크기의 행렬 A와 B 출력: 행렬 A와 B의 곱인 C 알고리즘: nxn_matrix strassen(int n, nxn matrix A, nxn matrix B){ if (n <= threshold) 단순한 알고리즘을 사용하여 C = A * B를 계산; else { A를 4개의 부분행렬 A11, A12, A21, A22로 분할; B를 4개의 부분행렬 B11, B12, B21, B22로 분할; 쉬트라쎈의 방법을 사용하여 C = A * B를 계산; // C 계산시에 다음과 같은 재귀 호출 사용: // M1=strassen(n/2, A11+A22, B11+B22) } return C; Threshold? 쉬트라쎈 알고리즘보다 단순 알고리즘이 더 좋을 것이라 예상되는 지점

쉬트라쎈(Strassen) 방법의 분석 (1/7) 곱셈 연산에 대한 시간복잡도 분석 단위연산: 곱셈하는 연산 입력크기: 행과 열의 수, n 1×1 행렬이 될 때까지 계속 분할한다고 가정. 두 개의 1×1 행렬의 곱은 그 비용이 1이다. threshold를 1이라고 가정 [모든 경우 시간복잡도] 분석 점화식을 다음과 같이 구할 수 있다. Why? 하나의 nxn 곱셈이 일곱 개의 (n/2)x(n/2) 곱셈으로 바뀌었기 때문

쉬트라쎈(Strassen) 방법의 분석 (2/7) 곱셈 연산에 대한 시간복잡도 분석 (계속) n=2k에 대해서 앞에서 구한 점화식을 전개하면 다음과 같다. 상기 결과는 귀납법에 의해서 증명이 가능하다. (Skip!) 또한, 상기 점화식은 Master Theorem 1번을 이용하면 간단히 해를 구할 수 있다. (See the next page)

쉬트라쎈(Strassen) 방법의 분석 (3/7) 곱셈 연산에 대한 시간복잡도 분석 (계속) n=2k에 대해서 앞에서 구한 점화식의 해를 Master Theorem 을 이용하여 구하기 f(n) = af(n/b) + cnd a=7, b=2, c=0, d=0  

쉬트라쎈(Strassen) 방법의 분석 (4/7) 덧셈/뺄셈 연산에 대한 시간복잡도 분석 단위연산: 덧셈/뺄셈하는 연산 입력크기: 행과 열의 수, n 모든 경우 시간복잡도 분석: 앞서와 마찬가지로 threshold를 1이라 한다. 점화식을 다음과 같이 구할 수 있다. nxn 곱셈이 일곱 개의 (n/2)x(n/2) 곱셈으로 바뀌었고, 18번의 (n/2)x(n/2) 행렬 덧셈/뺄셈이 필요한데, 각각은 (n/2)2 번의 덧셈/뺄셈을 필요로 하기 때문 Why?

쉬트라쎈(Strassen) 방법의 분석 (5/7) 덧셈/뺄셈 연산에 대한 시간복잡도 분석 (계속) 점화식은 다음과 같다. 부록 B의 예제 B.20을 이용하면 다음과 같이 점화식의 해가 구해진다. Master Theorem을 사용하면 상기 점화식의 해는 다음과 같이 구할 수 있다.   f(n) = af(n/b) + cnd a=7, b=2, c=9/2, d=2  

쉬트라쎈(Strassen) 방법의 분석 (6/7) 표 2.3 nxn 행렬을 곱하는 두 알고리즘의 비교 (p. 70) 단위 연산 표준 알고리즘 쉬트라센 알고리즘 곱셈 n3 n2.81 덧셈/뺄셈 n3 - n2 6n2.81 - 6n2

쉬트라쎈(Strassen) 방법의 분석 (7/7) Shmuel Winograd는 덧셈과 뺄셈을 15회만 수행하면 되는 쉬트라센 알고리즘의 변형을 개발 이후에 Coppersmith와 Winograd는 곱셈의 복잡도를 까지 낮춘 알고리즘을 개발하였다. 그렇다면, 과연 얼마까지 복잡도를 낮출 수 있을까? 두 행렬을 곱하기 위한 문제에 대해서 시간복잡도가 이 되는 알고리즘을 만들어 낸 사람은 아무도 없다. 게다가 그러한 알고리즘을 만들 수 없다고 증명한 사람도 아무도 없다.  

Skip… Chapter 2.6 Chapter 2.7

분할정복을 사용하지 말아야 하는 경우