검색어 입력폼

[공학]Strassen 알고리즘

저작시기 2007.01 |등록일 2007.06.03 한글파일한글 (hwp) | 5페이지 | 가격 1,200원

소개글

알고리즘 교과목 분할 및 정복 단원에서 다루는 Strassen 알고리즘 분석

목차

1. Strassen의 행렬식 곱셈 알고리즘의 등장
2. 알고리즘 : 두 정방 행렬의 곱셈
3. 알고리즘 : Strassen의 개선된 행렬 곱셈
4. 두 알고리즘의 복잡도 비교

본문내용

제 3장 분할 및 정복

3.3 Strassen의 행렬식 곱셈 알고리즘

1. Strassen의 행렬식 곱셈 알고리즘의 등장
두 개의 n x n정방 행렬(square matrix)의 곱셈의 알고리즘에서 곱셈의 회수에 대한 복잡도에 대하여, 1969년 Strassen은 스칼라의 곱셈 및 덧셈의 회수에 대한 복잡도가 개선된 알고리즘을 제안하였다.

2. 알고리즘 1.2 : 두 정방 행렬의 곱셈
1) 알고리즘 1.2
문제 : 두 개의 n x n 정방행렬에 대한 곱셈을 하시오.
입력 : 자연수 n, 그 대의 n x n 정방행렬 A 및 B
출력 : A 및 B를 곱한 결과 얻어지는 n x n 정방행렬 C

Void matrix_multiplication(int n, constnumber A[ ][ ], constnumber 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) 알고리즘 1.2 풀이
위의 알고리즘에서 n이 의미하는 것은 행렬의 크기이다. n의 값을 2로 놓고, 위의 알고리즘을 풀이 해 보겠다.
n = 2, i = 1, j = 1, k = 1, C[1][1]의 값을 0으로 초기화
→ C[1][1] = C[1][1]+A[1][1]*B[1][1]; …①
n = 2, i = 1, j = 1, k = 2, C[1][1]의 값은 ①
→ C[1][1] = C[1][1]+A[1][2]*B[2][1]; …②
i = 1, j = 1, k조건의 알고리즘 수행 후, C[1][1]은 ②의 값

n = 2, i = 1, j = 2, k = 1, C[1][2]의 값을 0으로 초기화
→ C[1][2] = C[1][2]+A[1][1]*B[1][2]; …③
n = 2, i = 1, j = 2, k = 2, C[1][2]의 값은 ③
→ C[1][2] = C[1][2]+A[1][2]*B[2][2]; …④
i = 1, j = 2, k조건의 알고리즘 수행 후, C[1][2]은 ④의 값
다운로드 맨위로